Breaking the quadratic gap for strongly polynomial solvers to combinatorial linear programs

Published on ● Video Link: https://www.youtube.com/watch?v=HfoJFOe1oaY



Duration: 1:00:19
937 views
18


Bento Natura (UC Berkeley & Georgia Tech)
https://simons.berkeley.edu/talks/bento-natura-uc-berkeley-georgia-tech-2023-11-30
Optimization and Algorithm Design

Recent years have seen tremendous progress in high-accuracy solvers for Maximum Flow, Minimum-Cost Flow and general Linear Programs (LP). Progress on strongly polynomial solvers for combinatorial LP on the other hand has stalled. For combinatorial LP beyond directed graphs this gap between exact and high-accuracy solvers is currently quadratic. We finally break the quadratic gap and design a strongly polynomial interior-point-method for combinatorial LP, which reduces the gap to only a linear factor.







Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Optimization and Algorithm Design
Bento Natura