There has been significant work recently on integer programs (IPs) min {cTx : Ax ≤ b, x ∈ ℤn } with a constraint marix A with bounded subdeterminants.
This is motivated by a well-known conjecture claiming that, for any constant positive integer Δ, Δ-modular IPs are efficiently solvable, which are IPs where the m by n constraint matrix A has full column rank and all n by n minors of A are within {-Δ, …, Δ}.
Previous progress on this question, in particular for Δ = 2, relies on algorithms that solve an important special case, namely strictly Δ-modular IPs, which further restrict the n by n minors of A to be within {-Δ, 0, Δ}.
Even for Δ = 2, such problems include well-known combinatorial optimization problems like the minimum odd/even cut problem.
The conjecture remains open even for strictly Δ-modular IPs. Prior advances were restricted to prime Δ, 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 one can check feasibility of strictly Δ-modular IPs in strongly polynomial time if Δ ≤ 4. |