- Series
- ACO Student Seminar
- Time
- Friday, November 18, 2022 - 1:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Bento Natura – Georgia Tech ISyE – b.natura@lse.ac.uk – https://personal.lse.ac.uk/natura/
- Organizer
- Abhishek Dhawan
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. The computational gap between high-accuracy solvers and strongly polynomial solvers is linear in the number of variables only for combinatorial LP on directed graphs. For combinatorial LP beyond directed graphs this gap is currently quadratic and is known since the 1980s due to a seminal result by Tardos.
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. Thus, we match the known linear gap for LP on directed graphs. Furthermore, we close the linear gap between feasibility and optimization of combinatorial LP.