Advances on strictly ∆-modular IPs
OPEN ACCESS
Loading...
Author / Producer
Date
2024-03
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
There has been significant work recently on integer programs (IPs) min {cᵀx : Ax ≤ b, x ∈ Zⁿ} with a constraint marix A with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any constant ∆ ∈ Z_>0, ∆-modular IPs are efficiently solvable, which are IPs where the constraint matrix A ∈ Zᵐ ˣ ⁿ has full column rank and all n x 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 x 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
210 (1-2)
Pages / Article No.
731 - 760
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Bounded subdeterminants; Congruency constraints; Integer programming; Group constraints; Total unimodularity
Organisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
Notes
This article is part of the special issue "Integer Programming and Combinatorial Optimization (IPCO) 2023".
Funding
184622 - Toward Stronger Approximation Algorithms for Fundamental Network Design and Optimization Problems (SNF)
817750 - Fundamental Problems at the Interface of Combinatorial Optimization with Integer Programming and Online Optimization (EC)
817750 - Fundamental Problems at the Interface of Combinatorial Optimization with Integer Programming and Online Optimization (EC)
Related publications and datasets
Is variant form of: