A Faster Algorithm for Linear Programming and the Maximum Flow Problem
Event details
| Date | 03.02.2015 |
| Hour | 16:00 › 17:00 |
| Speaker |
Yin Tat Lee, MIT |
| Location | |
| Category | Conferences - Seminars |
Abstract:
In this talk, I will present a new algorithm for solving linear programs. Given a linear program with n variables, m > n constraints, and bit complexity L, our algorithm runs in Õ(sqrt(n) L) iterations each consisting of solving Õ(1) linear systems and additional nearly linear time computation. Our method improves upon the convergence rate of previous state-of-the-art linear programming methods which required solving Õ(sqrt(m)L) linear systems. As a corollary, we achieve a running time of Õ(|E| sqrt(|V|)) for solving the maximum flow problem on a directed graph with |E| edges, |V| vertices, thereby improving upon the previous fastest running time Õ(|E|^(3/2)) and Õ(|E| |V|^(2/3)).
This talk reflects joint work with Aaron Sidford (See http://arxiv.org/abs/1312.6677 and http://arxiv.org/abs/1312.6713).
Short Bio:
Yin Tat Lee is a PhD student (under Professor Jonathan Kelner) at MIT, studying theoretical computer science. His areas of research span convex optimization, linear programming, spectral graph theory and algorithmic graph theory. He is particularly interested in combining convex optimization and combinatorial techniques to design fast algorithms for fundamental cut/flow problems. He is one of the recipients of the Best Paper Award at SODA 2014 for an almost-linear-time algorithm for approximate max flow in undirected graphs. Recently, Aaron Sidford and he resolved a long-standing open question for linear programming, which gives a faster interior point method and a faster exact min cost flow algorithm. This result receives the Best Paper Award, as well as the Best Student Paper Award of FOCS 2014.
In this talk, I will present a new algorithm for solving linear programs. Given a linear program with n variables, m > n constraints, and bit complexity L, our algorithm runs in Õ(sqrt(n) L) iterations each consisting of solving Õ(1) linear systems and additional nearly linear time computation. Our method improves upon the convergence rate of previous state-of-the-art linear programming methods which required solving Õ(sqrt(m)L) linear systems. As a corollary, we achieve a running time of Õ(|E| sqrt(|V|)) for solving the maximum flow problem on a directed graph with |E| edges, |V| vertices, thereby improving upon the previous fastest running time Õ(|E|^(3/2)) and Õ(|E| |V|^(2/3)).
This talk reflects joint work with Aaron Sidford (See http://arxiv.org/abs/1312.6677 and http://arxiv.org/abs/1312.6713).
Short Bio:
Yin Tat Lee is a PhD student (under Professor Jonathan Kelner) at MIT, studying theoretical computer science. His areas of research span convex optimization, linear programming, spectral graph theory and algorithmic graph theory. He is particularly interested in combining convex optimization and combinatorial techniques to design fast algorithms for fundamental cut/flow problems. He is one of the recipients of the Best Paper Award at SODA 2014 for an almost-linear-time algorithm for approximate max flow in undirected graphs. Recently, Aaron Sidford and he resolved a long-standing open question for linear programming, which gives a faster interior point method and a faster exact min cost flow algorithm. This result receives the Best Paper Award, as well as the Best Student Paper Award of FOCS 2014.
Practical information
- Informed public
- Free
Organizer
- Nisheeth Vishnoi