Knop, Dusan ;
Koutecky, Martin ;
Mnich, Matthias
Combinatorial nfold Integer Programming and Applications
Abstract
Many fundamental NPhard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra allows to solve ILPs in time that is exponential only in the dimension of the program. That algorithm therefore became a ubiquitous tool in the design of fixedparameter algorithms for NPhard problems, where one wishes to isolate the hardness of a problem by some parameter. However, it was discovered that in many cases using Lenstra’s algorithm has two drawbacks: First, the run time of the resulting algorithms is often doublyexponential in the parameter, and second, an ILP formulation in small dimension can not easily express problems which involve many different costs.
Inspired by the work of Hemmecke, Onn and Romanchuk [Math. Prog. 2013], we develop a singleexponential algorithm for socalled combinatorial nfold integer programs, which are remarkably similar to prior ILP formulations for various problems, but unlike them, also allow variable dimension. We then apply our algorithm to a few representative problems like Closest String, Swap Bribery, Weighted Set Multicover, and obtain exponential speedups in the dependence on the respective parameters, the input size, or both.
Unlike Lenstra’s algorithm, which is essentially a bounded search tree algorithm, our result uses the technique of augmenting steps. At its heart is a deep result stating that in combinatorial nfold IPs an existence of an augmenting step implies an existence of a “local” augmenting step, which can be found using dynamic programming. Our results provide an important insight into many problems by showing that they exhibit this phenomenon, and highlights the importance of augmentation techniques.
BibTeX  Entry
@InProceedings{knop_et_al:LIPIcs:2017:7861,
author = {Dusan Knop and Martin Koutecky and Matthias Mnich},
title = {{Combinatorial nfold Integer Programming and Applications}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {54:154:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7861},
URN = {urn:nbn:de:0030drops78616},
doi = {10.4230/LIPIcs.ESA.2017.54},
annote = {Keywords: integer programming, closest strings, fixedparameter algorithms}
}
01.09.2017
Keywords: 

integer programming, closest strings, fixedparameter algorithms 
Seminar: 

25th Annual European Symposium on Algorithms (ESA 2017)

Issue date: 

2017 
Date of publication: 

01.09.2017 