← List all talks ...

Interior Point Methods for Nearly Linear Time Algorithms

Aaron Sidford – Professor, Stanford

Thu, 6-May-2021 / 4:30pm / Zoom: https://stanford.zoom.us/meeting/register/tJckfuCurzkvEtKKOBvDCrPv3McapgP6HygJ

Talk

• Video

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). These results constitute the first polynomial time methods for solving these problems to high precision which run in nearly-linear time on sufficiently large and dense instances. No previous experience with interior point methods required.

This talk will touch upon joint work with Jan van den Brand, Yin Tat Lee, Yang P. Liu, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Zhao Song, and Di Wang including 2009.01802, 2002.02304, and 2101.05719.

Bio

Aaron Sidford is an assistant professor in the departments of Management Science and Engineering and Computer Science at Stanford University. He received his PhD from the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology, where he was advised by Jonathan Kelner. His research interests lie broadly in optimization, the theory of computation, and the design and analysis of algorithms, with an emphasis on work at the intersection of continuous optimization, graph theory, numerical linear algebra, and data structures. He is the recipient of a Microsoft Research Faculty Fellowship, a Sloan Research Fellowship, a NSF CAREER Award, a 2015 ACM Doctoral Dissertation Award honorable mention, FOCS 2015 and SODA 2014 best paper awards for work in these areas.