On the optimality of pseudo-polynomial algorithms for integer programming

Fomin, Fedor V. and Panolan, Fahad and Ramanujan, M. S. and et al, . (2022) On the optimality of pseudo-polynomial algorithms for integer programming. Mathematical Programming. ISSN 0025-5610

Full text not available from this repository. (Request a copy)


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Δ) mlog (Δ) 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. © 2022, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Panolan, Fahadhttps://orcid.org/0000-0001-6213-8687
Item Type: Article
Additional Information: A preliminary version of the paper appeared in the proceedings of 26th Annual European Symposium on Algorithms (ESA) 2018. This work is supported by the European Research Council (ERC) via grant LOPPRE, reference 819416, and the Norwegian Research Council via project MULTIVAL.
Uncontrolled Keywords: Algorithms and data structures; Integer programming
Subjects: Computer science
Mathematics > General principles of mathematics
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 25 Jul 2022 07:37
Last Modified: 25 Jul 2022 07:37
URI: http://raiith.iith.ac.in/id/eprint/9907
Publisher URL: http://doi.org/10.1007/s10107-022-01783-x
OA policy: https://v2.sherpa.ac.uk/id/publication/8102
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9907 Statistics for this ePrint Item