A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

Following the breakthrough work of Tardos (Oper. Res. ’86) in the bit-complexity model, Vavasis and Ye (Math. Prog. ’96) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) max c x, Ax = b, x ≥ 0, A ∈ m × n , Vavasis and Ye developed a primal-dual interior point method using a ‘layered least squares’ (LLS) step, and showed that O(n 3.5 log(χ A +n)) iterations suffice to solve (LP) exactly, where χ A is a condition measure controlling the size of solutions to linear systems related to A.