Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
Abstract
Recently, Allamigeon, Dadush, Loho, Natura, and Végh (ADLNV, SICOMP 2025) introduced an interior point method for linear programs whose number of iterations is bounded by the so-called straight line complexity (SLC) of the instance. This yields a strongly polynomial bound on the number of iterations of the corresponding interior point algorithm for broad classes of linear programs. In particular, in the companion paper we give a strongly polynomial straight line complexity bound for two-variable-per-inequality linear programs. However, in order to obtain a strongly polynomial algorithm for these classes, one also needs to address two important technical issues: initialization and bit-complexity bounds. Standard IPM initialization techniques either require numerical estimates that cannot be obtained in the strongly polynomial model, or involve modifying the instance in ways that do not preserve the geometry of the original LP, potentially affecting the SLC. In this work, we present an initialization framework for interior point methods for linear programming, along with a rounding procedure that ensures the continued feasibility of the IPM. We develop a multistage scheme in which each stage can be initialized in strongly polynomial time given the output of the previous stage. Additionally, we address the challenge of controlling the bit complexity of each iterate throughout the algorithm. To this end, we show that it is possible to represent iterates as low-complexity convex combinations of vertices and extreme rays. Our combinatorial rounding step is independent of the algorithm in ADLNV 2025, and can be applied more broadly in the context of path-following methods.
Related
- Strongly regular graph, strongly polynomial sequences, and two-level polynomials
- Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
- A bounded degree SDSOS hierarchy for solving SPLD polynomial programs
- Simple Strategy-Iteration with Dantzig's Rule is not Strongly Polynomial on Turn-Based Deterministic Games
- Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
BibTeX
@misc{dadush2026solving,
title = {{Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time}},
author = {Daniel Dadush and Zhuan Khye Koh and Bento Natura and Neil Olver and László A. Végh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26073},
eprint = {2610.26073},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26073},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
AU - Daniel Dadush
AU - Zhuan Khye Koh
AU - Bento Natura
AU - Neil Olver
AU - László A. Végh
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26073
UR - https://arxiv.org/abs/2610.26073
AB - Recently, Allamigeon, Dadush, Loho, Natura, and Végh (ADLNV, SICOMP 2025) introduced an interior point method for linear programs whose number of iterations is bounded by the so-called straight line complexity (SLC) of the instance. This yields a strongly polynomial bound on the number of iterations of the corresponding interior point algorithm for broad classes of linear programs. In particular, in the companion paper we give a strongly polynomial straight line complexity bound for two-variable-per-inequality linear programs. However, in order to obtain a strongly polynomial algorithm for these classes, one also needs to address two important technical issues: initialization and bit-complexity bounds. Standard IPM initialization techniques either require numerical estimates that cannot be obtained in the strongly polynomial model, or involve modifying the instance in ways that do not preserve the geometry of the original LP, potentially affecting the SLC. In this work, we present an initialization framework for interior point methods for linear programming, along with a rounding procedure that ensures the continued feasibility of the IPM. We develop a multistage scheme in which each stage can be initialized in strongly polynomial time given the output of the previous stage. Additionally, we address the challenge of controlling the bit complexity of each iterate throughout the algorithm. To this end, we show that it is possible to represent iterates as low-complexity convex combinations of vertices and extreme rays. Our combinatorial rounding step is independent of the algorithm in ADLNV 2025, and can be applied more broadly in the context of path-following methods.
ER -