Breaking the Quadratic Gap for Strongly Polynomial Solvers to Combinatorial Linear Programs

Explore a cutting-edge lecture on optimization and algorithm design that breaks new ground in solving combinatorial linear programs. Delve into Bento Natura's groundbreaking research from UC Berkeley and Georgia Tech, presented at the Simons Institute. Discover how this work bridges the gap between exact and high-accuracy solvers for combinatorial LP, reducing it from quadratic to linear. Learn about the innovative strongly polynomial interior-point method developed for combinatorial LP, which marks a significant advancement in the field. Gain insights into the recent progress in high-accuracy solvers for Maximum Flow, Minimum-Cost Flow, and general Linear Programs, and understand why progress on strongly polynomial solvers for combinatorial LP has been challenging. This hour-long talk offers a deep dive into the latest developments in optimization algorithms, providing valuable knowledge for researchers and practitioners in computer science and mathematics.