A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

Daniel Dadush, Sophie Huiberts, Bento Natura +1

Following the breakthrough work of Tardos in the bit-complexity model, Vavasis and Ye gave the first exact algorithm for linear programming in the real model of computation with ru…