Revisiting Tardos’s Framework for Linear Programming - Faster Exact Solutions using Approximate Solvers

Explore a 24-minute IEEE conference talk that delves into Tardos's framework for linear programming and presents innovative approaches for achieving faster exact solutions using approximate solvers. Learn about the distinctions between weakly and strongly polynomial algorithms, examine fast weakly polynomial algorithms for LP, and investigate strongly polynomial algorithms that depend solely on the constraint matrix. Discover the speakers' contributions, including the condition number A, proximity theorem, variable fixing for feasibility, the lifting operation, and both feasibility and optimization algorithms. Gain insights from Daniel Dadush, Bento Natura, and Laszlo Vegh as they revisit and expand upon Tardos's groundbreaking work in the field of linear programming.