Interior Point Methods for Nearly Linear Time Algorithms


Aaron Sidford May 13, 2021.


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). No previous experience with interior point methods required.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits
  • Limitations of Linear Cross-Entropy as a Measure of Quantum Advantage
  • Why we couldn't prove SETH hardness of CVP for even norms, Subset-SUM, and Many more!
  • Machine Learning for Quantum Many-body Physics
  • Brooks' Theorem in Graph Streams, A Single-Pass Semi-Streaming Algorithm for Δ-Coloring