The Library
On the optimality of pseudo-polynomial algorithms for integer programming
Tools
Fomin, Fedor V., Panolan, Fahad, Ramanujan, Maadapuzhi Sridharan and Saurabh, Saket (2023) On the optimality of pseudo-polynomial algorithms for integer programming. Mathematical Programming Series B, 198 . pp. 561-593. doi:10.1007/s10107-022-01783-x ISSN 0025-5610.
|
PDF
WRAP-On-optimality-pseud0-polynomial-algrithms-integer-programming-2022.pdf - Accepted Version - Requires a PDF viewer. Download (726Kb) | Preview |
Official URL: https://doi.org/10.1007/s10107-022-01783-x
Abstract
In the classic Integer Programming Feasibility (IPF) problem, the objective is to decide whether, for a given m×n matrix A and an m-vector b=(b1,…,bm), there is a non-negative integer n-vector x such that Ax=b. Solving (IPF) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input.
The classic pseudo-polynomial time algorithm of Papadimitriou [J. ACM 1981] for instances of (IPF) with a constant number of constraints was only recently improved upon by Eisenbrand and Weismantel [SODA 2018] and Jansen and Rohwedder [ITCS 2019]. Jansen and Rohwedder designed an algorithm for (IPF) with running time O(mΔ)m log(Δ)log(Δ+∥b∥∞)+O(mn). Here, Δ is an upper bound on the absolute values of the entries of A. We continue this line of work and show that under the Exponential Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal, by proving a lower bound of no(mlogm)⋅∥b∥o(m)∞. We also prove that assuming ETH, (IPF) cannot be solved in time f(m)⋅(n⋅∥b∥∞)o(mlogm) for any computable function f.
This motivates us to pick up the line of research initiated by Cunningham and Geelen [IPCO 2007] who studied the complexity of solving (IPF) with non-negative matrices in which the number of constraints may be unbounded, but the branch-width of the column-matroid corresponding to the constraint matrix is a constant. We prove a lower bound on the complexity of solving (IPF) for such instances and obtain optimal results with respect to a closely related parameter, path-width. Specifically, we prove matching upper and lower bounds for (IPF) when the path-width of the corresponding column-matroid is a constant.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Integer programming, Computational complexity, Algorithms | ||||||||
Journal or Publication Title: | Mathematical Programming Series B | ||||||||
Publisher: | Springer | ||||||||
ISSN: | 0025-5610 | ||||||||
Official Date: | March 2023 | ||||||||
Dates: |
|
||||||||
Volume: | 198 | ||||||||
Page Range: | pp. 561-593 | ||||||||
DOI: | 10.1007/s10107-022-01783-x | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Reuse Statement (publisher, data, author rights): | "This version of the article has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10107-022-01783-x. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/acceptedmanuscript-terms”." | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 25 April 2022 | ||||||||
Date of first compliant Open Access: | 14 February 2023 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year