Jansen, Klaus ;
Lassota, Alexandra ;
Rohwedder, Lars
NearLinear Time Algorithm for nfold ILPs via Color Coding
Abstract
We study an important case of ILPs max {c^Tx  Ax = b, l <= x <= u, x in Z^{n t}} with n * t variables and lower and upper bounds l, u in Z^{nt}. In nfold ILPs nonzero entries only appear in the first r rows of the matrix A and in small blocks of size s x t along the diagonal underneath. Despite this restriction many optimization problems can be expressed in this form. It is known that nfold ILPs can be solved in FPT time regarding the parameters s, r, and Delta, where Delta is the greatest absolute value of an entry in A. The stateoftheart technique is a local search algorithm that subsequently moves in an improving direction. Both, the number of iterations and the search for such an improving direction take time Omega(n), leading to a quadratic running time in n. We introduce a technique based on Color Coding, which allows us to compute these improving directions in logarithmic time after a single initialization step. This leads to the first algorithm for nfold ILPs with a running time that is nearlinear in the number nt of variables, namely (rs Delta)^{O(r^2s + s^2)} L^2 * nt log^{O(1)}(nt), where L is the encoding length of the largest integer in the input. In contrast to the algorithms in recent literature, we do not need to solve the LP relaxation in order to handle unbounded variables. Instead, we give a structural lemma to introduce appropriate bounds. If, on the other hand, we are given such an LP solution, the running time can be decreased by a factor of L.
BibTeX  Entry
@InProceedings{jansen_et_al:LIPIcs:2019:10651,
author = {Klaus Jansen and Alexandra Lassota and Lars Rohwedder},
title = {{NearLinear Time Algorithm for nfold ILPs via Color Coding}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {75:175:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10651},
URN = {urn:nbn:de:0030drops106518},
doi = {10.4230/LIPIcs.ICALP.2019.75},
annote = {Keywords: NearLinear Time Algorithm, nfold ILP, Color Coding}
}
04.07.2019
Keywords: 

NearLinear Time Algorithm, nfold ILP, Color Coding 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 