A New Approach to Strongly Polynomial Linear Programming.
Mihály Bárász, Santosh Vempala · 2010
Abstract: We present an affine-invariant approach for solving linear programs. Unlike previous approaches, the potential strong polynomiality of the new approach does not require that graphs of polytopes have polynomial diameter (the Hirsch conjecture or weaker versions). We prove that two natural realizations of the approach work efficiently for deformed products [AZ99], a class of polytopes that generalizes all known difficult examples for variants of the simplex method, e.g., the Klee-Minty [KM72] and Goldfarb-Sit [GS79] cubes.