Aaron Sidford: Path Finding Methods for Linear Programming

In this talk, I will present a new algorithm for solving linear programs. Whereas the worst case convergence rate of previous state of the art linear programming algorithms depended on the larger of the number of variables and the number of constraints, our algorithms depend only the smaller (up to polylogarithmic factors).

While this talk will be focused on linear programming techniques, I will motivate this study through the maximum flow problem. In particular, I will explain how the techniques presented can be used to achieve a running time of Õ(m sqrt(n) log^2(U)) for solving both the maximum flow and the more general minimum cost flow problems on directed graph with m edges, n vertices, and capacity ratio U, thereby improving upon the previous fastest running time for solving these problems in the slightly dense regime.

This talk will assume no previous exposure to linear programming algorithms, convex optimization, or graph theory and will cover much of the basics regarding path following methods for solving linear programs.

This talk reflects joint work with Yin Tat Lee.