Iterative Methods, Combinatorial Optimization, and Linear Programming Beyond the Universal Barrier

Over the past decade there has been a revolution in the field of algorithmic graph theory. Using techniques from disparate areas of computer science, ranging from numerical analysis, to data structures, to continuous optimization, there have been numerous breakthroughs in improving the running time for solving classic problems in combinatorial optimization. 

 

In this talk I will discuss my work in this area and show how it has led to both improved running times for solving fundamental problems in combinatorial optimization and the creation of improved iterative methods for solving classic continuous optimization problems. After briefly discussing this high-level research program, I will provide a more detailed illustration through my recent work on linear programming and the maximum flow problem. 

 

In particular, I will present a new algorithm for solving linear programs that improves upon the convergence rate of previous state-of-the-art methods. Where the convergence rate of the previous efficient methods depended on the larger of the number of variables and the number of constraints ours depends on the smaller. Our algorithm approximately matches the convergence rate of the "universal barrier" of Nesterov and Nemirovskii while greatly decreasing the iteration costs. Furthermore, I will discuss how our method outperforms the universal barrier in particular cases, yielding the fastest known running times for solving dense instances of the directed maximum flow problem) and more generally, minimum cost flow. 

 

This talk will assume no previous experience with linear programming algorithms, convex optimization, or graph theory.

 

Aaron Sidford is a PhD student in the electrical engineering and computer science department at the Massachusetts Institute of Technology, advised by Jonathan Kelner. His research interests lie broadly in the theory of computation and the design of efficient algorithms. He is particularly interested in problems at the intersection of combinatorial optimization and numerical analysis. Since he began his PhD in 2011, his research has focused on improving the running time for solving classic problems in algorithmic graph theory while using and improving tools ranging from convex analysis to data structures to spectral graph theory.