Fomin, Fedor V. ;
Panolan, Fahad ;
Ramanujan, M. S. ;
Saurabh, Saket
On the Optimality of Pseudopolynomial 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 mvector b=(b_1,..., b_m), there is a nonnegative integer nvector 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 pseudopolynomial 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 nonnegative, 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 nonnegative matrices in which the number of constraints may be unbounded, but the branchwidth of the columnmatroid 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, pathwidth. Specifically, we prove matching upper and lower bounds for (IP) when the pathwidth of the corresponding columnmatroid 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 Pseudopolynomial Algorithms for Integer Programming}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {31:131:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9494},
URN = {urn:nbn:de:0030drops94949},
doi = {10.4230/LIPIcs.ESA.2018.31},
annote = {Keywords: Integer Programming, Strong Exponential Time Hypothesis, Branchwidth of a matrix, Finegrained Complexity}
}
2018
Keywords: 

Integer Programming, Strong Exponential Time Hypothesis, Branchwidth of a matrix, Finegrained Complexity 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 