Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers

Daniel Dadush, Bento Natura, László A. Végh

In breakthrough work, Tardos (Oper. Res. '86) gave a proximity based framework for solving linear programming (LP) in time depending only on the constraint matrix in the bit comple…