Speaker
Bento Natura
UC Berkeley & Georgia Tech
Topic
The computational complexity of Interior Point Methods for Fast Exact Linear Programming
The existence of a strongly polynomial algorithm for linear programs (LP) is one of the most important open problems in theoretical computer science and beyond. The last decades have seen tremendous progress for special subclasses of LP (e.g., minimum cost flow, multi-commodity flow, and discounted Markov decision processes) whose proofs of strong polynomiality rely on very different ideas, algorithms and techniques. Together with Allamigeon, Dadush, Loho, and Végh (FOCS 2022) Natura devised an interior point method that runs in strongly polynomial time whenever a certain notion called straight line complexity is polynomially bounded. Taking this algorithm as a blackbox, Natura shows how strong polynomiality for many of the subclasses of LP can be recovered. While this settles the polynomiality of interior point methods (IPM) for certain LP subclasses, it does not inherently address their precise computational complexity. Natura will touch on approaches to speed up these algorithms, aiming to align their performance with that of fast, approximate methods.
Zoom-Link for online participation: https://cwi-nl.zoom.us/j/87542191297?pwd=QTIxYlNQUmQ5UTFKb0NSaVVsbGFJZz09
