An Affine-invariant Algorithm for Linear Programming

Santosh Vempala
Georgia Institute of Technology
Computer Science

We present an affine-invariant approach for solving linear programs. Similar to variants of the simplex method, the new approach also moves from vertex to vertex of the input polytope, improving the objective value. However, unlike previous approaches, it takes non-edge shortcuts and its *potential* strong polynomiality does not require that graphs of polytopes have polynomial diameter (the weak Hirsch conjecture). We prove that two natural
realizations of the approach are efficient for deformed products [Amenta and Ziegler, 1999], a class of polytopes
that generalizes all known difficult examples for variants of the simplex method, e.g., the Klee-Minty and Goldfarb-Sit cubes.

This is joint work with Mihaly Barasz.

Presentation (PowerPoint File)

Back to Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?