Sparse Integer Programming Is Fixed-Parameter Tractable

Friedrich Eisenbrand (), Christoph Hunkenschröder (), Kim-Manuel Klein (), Martin Koutecký (), Asaf Levin () and Shmuel Onn ()
Additional contact information
Friedrich Eisenbrand: EPFL SB MATH DISOPT, 1015 Lausanne, Switzerland
Christoph Hunkenschröder: Institut für Mathematik, Technische Universität Berlin, D-10623 Berlin, Germany
Kim-Manuel Klein: Institut für Theoretische Informatik, Universität zu Lübeck, 23538 Lübeck, Germany
Martin Koutecký: Computer Science Institute, Faculty of Mathematics and Physics, Charles University, 118 00 Praha 1, Czech Republic
Asaf Levin: Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology, Technion City, Haifa 3200003, Israel
Shmuel Onn: Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology, Technion City, Haifa 3200003, Israel

Mathematics of Operations Research, 2025, vol. 50, issue 3, 2141-2156

Abstract: We study the general integer programming problem where the number of variables n is a variable part of the input. We consider two natural parameters of the constraint matrix A : its numeric measure a and its sparsity measure d . We present an algorithm for solving integer programming in time g ( a , d ) poly ( n , L ) , where g is some computable function of the parameters a and d , and L is the binary encoding length of the input. In particular, integer programming is fixed-parameter tractable parameterized by a and d , and is solvable in polynomial time for every fixed a and d . Our results also extend to nonlinear separable convex objective functions.

Keywords: 90C10; 68Q27; integer programming; parameterized complexity; Graver basis; treedepth; n -fold; tree-fold; 2-stage stochastic; multistage stochastic (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2023.0162 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:3:p:2141-2156

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().