How Close is Close Enough? Solving Linear Programs When Rounding Just Won't Cut It!
summary
Shows that linear programs whose constraint normals are 2-sparse constraints admit a new algorithm that runs in strongly polynomial many arithmetic operations (add, multiply, compare, and space), closing a parameterized gap before the general LP question. Contrasts this with the irrational-coefficient barrier where path-following methods can take 2^n worst-case steps. Delivers the first strongly polynomial exact solver for bipartite assignment-style problems with multiplicative ability/cost factors and explains the combinatorial reductions used.
AI-written summary · about