Koutecký, Martin ;
Levin, Asaf ;
Onn, Shmuel
A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
Abstract
The theory of nfold integer programming has been recently emerging as an important tool in parameterized complexity. The input to an nfold integer program (IP) consists of parameter A, dimension n, and numerical data of binary encoding length L. It was known for some time that such programs can be solved in polynomial time using O(n^{g(A)}L) arithmetic operations where g is an exponential function of the parameter. In 2013 it was shown that it can be solved in fixedparameter tractable time using O(f(A)n^3L) arithmetic operations for a singleexponential function f. This, and a faster algorithm for a special case of combinatorial nfold IP, have led to several very recent breakthroughs in the parameterized complexity of scheduling, stringology, and computational social choice. In 2015 it was shown that it can be solved in strongly polynomial time using O(n^{g(A)}) arithmetic operations.
Here we establish a result which subsumes all three of the above results by showing that nfold IP can be solved in strongly polynomial fixedparameter tractable time using O(f(A)n^6 log n) arithmetic operations. In fact, our results are much more general, briefly outlined as follows.
 There is a strongly polynomial algorithm for integer linear programming (ILP) whenever a socalled Graverbest oracle is realizable for it.
 Graverbest oracles for the large classes of multistage stochastic and treefold ILPs can be realized in fixedparameter tractable time. Together with the previous oracle algorithm, this newly shows two large classes of ILP to be strongly polynomial; in contrast, only few classes of ILP were previously known to be strongly polynomial.
 We show that ILP is fixedparameter tractable parameterized by the largest coefficient A _infty and the primal or dual treedepth of A, and that this parameterization cannot be relaxed, signifying substantial progress in understanding the parameterized complexity of ILP.
BibTeX  Entry
@InProceedings{kouteck_et_al:LIPIcs:2018:9089,
author = {Martin Kouteck{\'y} and Asaf Levin and Shmuel Onn},
title = {{A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {85:185:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9089},
URN = {urn:nbn:de:0030drops90898},
doi = {10.4230/LIPIcs.ICALP.2018.85},
annote = {Keywords: integer programming, parameterized complexity, Graver basis, nfold integer programming}
}
04.07.2018
Keywords: 

integer programming, parameterized complexity, Graver basis, nfold integer programming 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 