Layered-Least-Squares Interior Point Methods: A Combinatorial Optimization Perspective

Algorithms Seminar
Speaker Name
Laci Vegh
Date and Time
Talk will be virtual on Zoom

A famous 1986 result by Tardos on combinatorial linear programs showed that a linear program can be 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 significantly strengthened by Vavasis and Ye in 1996, who gave a 'layered least squares' (LLS) interior-point method, that terminates with an exact optimal solution in O(n^{3.5} log(\bar\chi_A+n)) iterations, where \bar\chi_A is a certain condition number associated with the (not necessarily integer) constraint matrix 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 \bar\chi^*_A, defined as the minimum \bar\chi_{AD} value achievable by a column rescaling AD of A, and gave strong evidence that this should be the case. We resolve this question in the affirmative, by giving a new LLS interior-point method that terminates in  O(n^{2.5} log(\bar\chi_A^*+n)) iterations.

The main insight is a new, combinatorial characterization of the condition number \bar\chi. We show that this can be well approximated with a certain 'circuit imbalance measure'. Using techniques of matroid theory, we give an efficient algorithm for finding a nearly optimal column rescaling.  Further, we develop a scaling invariant LLS algorithm, together with a refined potential function based analysis for LLS algorithms in general. 

In the talk, I will give a self-contained introduction of LLS interior-point methods from a combinatorial optimization perspective. This is based on joint work with Daniel Dadush, Sophie Huiberts, and Bento Natura.

Short Biography

László Végh is a professor in the Mathematics Department at the London School of Economics. He received his Ph.D. from Eötvös University, Budapest in 2010. Before joining LSE, he was a postdoc at Georgia Tech in 2011-12. He is broadly interested in algorithms and optimisation: exact and approximation algorithms for problems related to network design, flows, matchings, and equilibrium computation, with a particular focus on strongly polynomial computability.

Anilesh Krishnaswamy