Interior Point Methods for Nearly Linear Time Algorithms

Speaker

Aaron Sidford May 13, 2021.

Abstract

Linear programming is a foundational continuous optimization problem and special cases, e.g. maximum cardinality bipartite matching, are among the most fundamental problems in combinatorial optimization. In this talk, I will survey recent advances in solving these problems using interior point methods. I will discuss how new interior point methods can be leveraged to efficiently reduce these problems to data structures problems which can be solved efficiently with techniques from randomized numerical linear algebra and graph theory. This talk will highlight recent joint work which showed that linear programs with d variables and n constraints can be solved with high probability to high precision in time Otilde(nd + poly(d)) and that a variety of graph problems, e.g. maximum flow and optimal transport, on n-node -m-edge graphs can be solved to with high probability to high precision in time Otilde(m + n^1.5). No previous experience with interior point methods required.