Advances on strictly Δ-modular IPs

• 成果类型: Article
• 署名作者: Nagele, Martin; Nobel, Christian; Santiago, Richard; Zenklusen, Rico
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02148-2
• 发表日期: 2025
• 页码: 731-760
• 关键词: polynomial algorithms

摘要

There has been significant work recently on integer programs (IPs) min{c(inverted perpendicular)x: Ax <= b, x is an element of Z(n)} with a constraint marix A with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any constant Delta is an element of Z(>0), Delta-modular IPs are efficiently solvable, which are IPs where the constraint matrix A is an element of Z(mxn) has full column rank and all n x n minors of A are within {-Delta, . . . ,Delta}. Previous progress on this question, in particular for Delta = 2, relies on algorithms that solve an important special case, namely strictly Delta-modular IPs, which further restrict the n x n minors of A to be within {-Delta, 0, Delta}. Even for Delta = 2, such problems include well-known combinatorial optimization problems like the minimum odd/even cut problem. The conjecture remains open even for strictly Delta-modular IPs. Prior advances were restricted to prime Delta, which allows for employing strong number-theoretic results. In this work, we make first progress beyond the prime case by presenting techniques not relying on such strong number-theoretic prime results. In particular, our approach implies that there is a randomized algorithm to check feasibility of strictly Delta-modular IPs in strongly polynomial time if Delta <= 4.