On Integer Programming, Discrepancy, and Convolution

Klaus Jansen () and Lars Rohwedder ()
Additional contact information
Klaus Jansen: University of Kiel, 24118 Kiel, Germany
Lars Rohwedder: Maastricht University, 6211 LK Maastricht, Netherlands

Mathematics of Operations Research, 2023, vol. 48, issue 3, 1481-1495

Abstract: Integer programs with a fixed number of constraints are solvable in pseudo-polynomial time in the largest coefficient of any constraint. We give a new algorithm which improves the running time of the state of the art. Moreover, we show that improving on our algorithm for any number of constraints is equivalent to improving over the quadratic time algorithm for (min, +)-convolution. This is strong evidence that our algorithm’s running time is the best possible. We also present a specialized algorithm for testing the feasibility of an integer program and give a tight lower bound, which is based on the strong exponential time hypothesis in this case.

Keywords: Primary: 90C10; fixed-parameter tractable; fine-grained complexity; dynamic programming (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1308 (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:48:y:2023:i:3:p:1481-1495

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 ().