Nicole Hedblom: Random Edge is not faster than Random Facet on Linear Programs
Time: Wed 2023-05-24 10.00
Location: 3721, Lindstedsvägen 25 and Zoom
Video link: Meeting ID: 685 9929 2593
Abstract:
A Linear Program is a problem where the goal is to maximize a linear function subject to a set of linear inequalities. Geometrically, this can be rephrased as finding the highest point on a polyhedron. The Simplex method is a commonly used algorithm to solve Linear Programs. It traverses the vertices of the polyhedron, and in each step, it selects one adjacent better vertex and moves there. There can be multiple vertices to choose from, and therefore the Simplex method has different variants deciding how the next vertex is selected. One of the most natural variants is Random Edge, which in each step of the Simplex method uniformly at random selects one of the better adjacent vertices.
It is interesting and non-trivial to study the complexity of variants of the Simplex method in the number of variables, d, and inequalities, N. In 2011, Friedmann, Hansen, and Zwick found a class of Linear Programs for which the Random Edge algorithm is subexponential with complexity 2^Ω(N^(1/4)), where d=O(N). Previously all known lower bounds were polynomial. We give an improved lower bound of 2^Ω(N^(1/2)), for Random Edge on Linear Programs where the number of inequalities and variables are both O(N).
Another well studied variant of the Simplex method is Random Facet. It is upper bounded by 2^O(N^(1/2)) and 2^O(d^(1/2)). Thus we prove that Random Edge is not faster than Random Facet on Linear Programs.
Our construction is very similar to the previous construction of Friedmann, Hansen and Zwick. We construct a Markov Decision Process which behaves like a binary counter with linearly many levels and linearly many nodes on each level. The new idea is a new type of delay gadget which can switch quickly from 0 to 1 in some circumstances, leading to fewer nodes needed on each level of the construction. The key idea is that it is worth taking a large risk of getting a small negative reward if the potential positive reward is large enough in comparison.