Totally Δ-modular IPs with two non-zeros in most rows

• 成果类型: Article; Early Access
• 署名作者: Kober, Stefan
• 署名单位: Universite Libre de Bruxelles
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02388-4
• 发表日期: 2026-06-22
• 关键词: integer programming; Parametrized integer programming; Subdeterminants; Structural graph theory; dynamic programming; strongly polynomial algorithm

摘要

Integer programs (IPs) on constraint matrices with bounded subdeterminants are conjectured to be solvable in polynomial time. We give a strongly polynomial-time algorithm to solve IPs where the constraint matrix has bounded subdeterminants and at most two non-zeros per row after removing a constant number of rows and columns. This result extends the work by Fiorini, Joret, Weltge & Yuditsky (J. ACM 72(1), 1-50 (2025)) by allowing for additional, unifying constraints and variables. Further, we give a randomized polynomial-time algorithm for the natural transposed case, i.e., where the main part of the matrix has two non-zeros per column instead of per row.