Combinatorics Seminar
When: Sunday, December 20, 10am
Where: Schreiber 309
Speaker: Uri Zwick, Tel Aviv University
Title: Random-Edge is not faster than Random-Facet on abstract cubes
Abstract:
Random-Edge and Random-Facet are two very natural randomized pivoting
rules for the simplex algorithm. The behavior of Random-Facet is
fairly well understood. It performs an expected sub-exponential number
of pivoting steps on any linear program, or more generally, on any
Acyclic Unique Sink Orientation (AUSO) of an arbitrary polytope,
making it the fastest known pivoting rule for the simplex algorithm.
The behavior of Random-Edge is much less understood.
We show that in the AUSO setting, Random-Edge is not faster than
Random-Facet. To do that, we construct AUSOs of the n-dimensional
hypercube on which Random-Edge performs an expected number of
2^{\Omega(\sqrt{n})} steps. This improves on a 2^{\Omega(\sqrt[3]{n})}
lower bound of Matousek and Szabo from 2004. As Random-Facet
performs an expected number of 2^{O(\sqrt{n})} steps on any
n-dimensional AUSO, this establishes our result.
Joint work with Thomas Dueholm Hansen.