2023/02/14 by Martin Nägele, Nägele, Martin, Christian Nöbel +5 · 2 citations
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2302.07029
openalex publication_date 2023/02/14 · openalex created_date 2023/02/17 · openalex updated_date 2026/07/30
There has been significant work recently on integer programs (IPs) min\c^\top x \colon 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 Δ∈ ℤ>0, Δ-modular IPs are efficiently solvable, which are IPs where the constraint matrix A∈ ℤm× n has full column rank and all n× 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× 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 there is a randomized algorithm to check feasibility of strictly Δ-modular IPs in strongly polynomial time if Δ≤4.