License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.31
URN: urn:nbn:de:0030-drops-94949
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9494/
Fomin, Fedor V. ;
Panolan, Fahad ;
Ramanujan, M. S. ;
Saurabh, Saket
On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
Abstract
In the classic Integer Programming (IP) problem, the objective is to decide whether, for a given m x n matrix A and an m-vector b=(b_1,..., b_m), there is a non-negative integer n-vector x such that Ax=b. Solving (IP) 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 (IP) with a constant number of constraints was only recently improved upon by Eisenbrand and Weismantel [SODA 2018] and Jansen and Rohwedder [ArXiv 2018]. We continue this line of work and show that under the Exponential Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal. We also show that when the matrix A is assumed to be non-negative, a component of Papadimitriou's original algorithm is already nearly optimal under ETH.
This motivates us to pick up the line of research initiated by Cunningham and Geelen [IPCO 2007] who studied the complexity of solving (IP) 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 (IP) 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 (IP) when the path-width of the corresponding column-matroid is a constant.
BibTeX - Entry
@InProceedings{fomin_et_al:LIPIcs:2018:9494,
author = {Fedor V. Fomin and Fahad Panolan and M. S. Ramanujan and Saket Saurabh},
title = {{On the Optimality of Pseudo-polynomial Algorithms for Integer Programming}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {31:1--31:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-081-1},
ISSN = {1868-8969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9494},
URN = {urn:nbn:de:0030-drops-94949},
doi = {10.4230/LIPIcs.ESA.2018.31},
annote = {Keywords: Integer Programming, Strong Exponential Time Hypothesis, Branch-width of a matrix, Fine-grained Complexity}
}
|
Keywords: |
|
Integer Programming, Strong Exponential Time Hypothesis, Branch-width of a matrix, Fine-grained Complexity |
|
Collection: |
|
26th Annual European Symposium on Algorithms (ESA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
14.08.2018 |
