Abstract
The existence of a strongly polynomial algorithm for linear programs (LP) is one of the most important open problems in theoretical computer science. The last decades have seen tremendous progress for special subclasses of LP (e.g., minimum cost flow, multi-commodity flow, discounted Markov decision processes) whose proofs of strong polynomiality rely on very different ideas, algorithms and techniques. Together with Allamigeon, Dadush, Loho, and Végh (FOCS 2022) we devised an interior point method that runs in strongly polynomial time whenever a certain curvature is polynomially bounded. Taking this algorithm as a blackbox, we show how strong polynomiality for many of the subclasses of LP can be recovered.