László Végh - Linear programming and circuit imbalances

The lectures will study special classes of linear programs that can be solved in strongly polynomial time, combining perspectives from continuous and combinatorial optimization. A famous 1986 result by Tardos on “combinatorial linear programs” showed that a linear program can be exactly solved in poly(n,m,log Delta) arithmetic operations, where Delta is the maximum subdeterminant of the integer constraint matrix. Note that this bound is independent from the right hand side and the cost vector. This was strengthened by Vavasis and Ye in 1996, who gave a ‘layered least squares’ (LLS) interior-point method with running time polynomial in n, m, and a certain condition number of the constraint matrix. The result enhances standard interior point methods using beautiful combinatorial ideas.
Recent work has focused on the `circuit imbalance measure’ of a matrix: this is the largest ratio between the absolute values between the nonzero entries of a support minimal vector in the kernel of the matrix. The lectures will explore the combinatorics and proximity theory of circuits, and present stronger variants of the Tardos and Vavasis-Ye results from this perspective.