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

arXiv: https://arxiv.org/abs/1912.06252 · HTML: https://mlsanity.com/paper/1912.06252/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2019.

## Built on by (most cited first, 1 of 1)

- [A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning](https://mlsanity.com/paper/2212.03008/) (2022)

## Abstract (arXiv)

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.