AMS Seminar: Daniel Dadush (Centrum Wiskunde & Informatica (CWI), Netherlands) @ Whitehead 304

Title: A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
Abstract: 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 cx,Ax=b,x>=0,A in R^{mxn}, Vavasis and Ye developed a primal-dual interior point method using a ‘layered least squares’ (LLS) step, and showed that O(n^3.5log(chi(A))) iterations suffice to solve (LP) exactly, where chi(A) 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 chi*(A), defined as the minimum chi(AD) 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(m^2n^2+n^3) time algorithm which works on the linear matroid of A to compute a nearly optimal diagonal rescaling D satisfying chi(AD)≤n(chi*(A))3. This algorithm also allows us to approximate the value of chi(A) up to a factor n(chi*(A))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(n^{2.5}logn log(chi*(A))) iteration bound for optimally solving (LP) using our algorithm. The same argument also yields a factor n/logn improvement on the iteration complexity bound of the original Vavasis-Ye algorithm.
>