For fixed Δ and fixed k, every integer program on a totally Δ-modular matrix with at most two non-zero entries per row outside k extra rows and columns can be solved in strongly polynomial time.
ACM-SIAM Sym- posium on Discrete Algorithms (SODA25) (2025)
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2024 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Totally $\Delta$-modular IPs with two non-zeros in most rows
For fixed Δ and fixed k, every integer program on a totally Δ-modular matrix with at most two non-zero entries per row outside k extra rows and columns can be solved in strongly polynomial time.