Breaking the quadratic gap for strongly polynomial solvers to combinatorial linear programs
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=HfoJFOe1oaY
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.
Other Videos By Simons Institute for the Theory of Computing
Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Optimization and Algorithm Design
Bento Natura