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

Following the breakthrough work of Tardos in the bit-complexity model, Vavasis and Ye 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^top 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(n3.5 log (barchiA+n)) iterations suffice to solve (LP) exactly, where barchiA is a condition measure controlling the size of solutions to linear systems related to A. Monteiro and Tsuchiya, noting that the central path is invariant under rescalings of the columns of A and c, asked whether there exists an LP algorithm depending instead on the measure barchi^*A, defined as the minimum barchiAD value achievable by a column rescaling AD of A, and gave strong evidence that this should be the case. We resolve this open question affirmatively. Our first main contribution is an O(m2 n2 + n3) time algorithm which works on the linear matroid of A to compute a nearly optimal diagonal rescaling D satisfying barchiAD ≤ n(barchi^*)3. This algorithm also allows us to approximate the value of barchiA up to a factor n (barchi^*)2. As our second main contribution, we develop a scaling invariant LLS algorithm, together with a refined potential function based analysis for LLS algorithms in general. With this analysis, we derive an improved O(n2.5 log nlog (barchi^*A+n)) iteration bound for optimally solving (LP) using our algorithm. The same argument also yields a factor n/log n improvement on the iteration complexity bound of the original Vavasis-Ye algorithm.