Fast algorithms for linear programs and bipartite matching via new data structures and interior-point methods

Abstract: Linear Programs (LPs) capture many optimization problems such as shortest paths or bipartite matching. In the past years, there have been substantial improvements for LP solvers, resulting in algorithms that run in nearly linear time for dense LPs and dense graphs. In this talk, I will explain how these improvements came to be from an interplay of interior point methods and dynamic algorithms (data structures).

Interior point methods can be seen as a framework for constructing iterative algorithms that solve linear programs. Like many other iterative algorithms, they can be sped up via data structures that efficiently maintain the intermediate solution in each iteration. Recent advances in the area of dynamic algorithms (data structures) showed that LP solvers could be improved if the interior point method could be made more robust against approximation errors.

So while the interior point method motivates research in the area of dynamic algorithms, results in dynamic algorithms also motivated further research on interior-point methods. This cycle leads to repeated improvements in both areas and eventually resulted in nearly linear time solvers for dense LPs and nearly linear time algorithms for bipartite matching on moderately dense graphs.