Advances on strictly Δ-modular IPs

• 成果类型: Article; Early Access
• 署名作者: 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
• 发表日期: 2024
• 关键词: strongly polynomial algorithm

摘要

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 Zmxn has full column rank and all nxn minors of A are within {-Delta,& mldr;,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 nxn 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. Similar content being vi