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.

Intro
Linear Programming
Weakly vs Strongly Polynomial Algorithms for
Fast Weakly Polynomial Algorithms for LP
Strongly Polynomial Algorithms for LP
Dependence on the constraint matrix only
Tardos's framework: variable fixing
Our contributions: Dadush-N.-Végh '20
The condition number A
Proximity theorem
Variable fixing for feasibility
The lifting operation
The feasibility algorithm
Optimization algorithm