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.
Copyright. All Rights Reserved.