Combinatorial n-fold Integer Programming and Applications
Authors:
- Dušan KnopDKDušan Knop
- Martin KouteckýMKMartin Koutecký
- Matthias MnichMMMatthias Mnich
Preprint
Abstract
Integer Linear Programming is a famous NP-complete problem. Lenstra showed that in the case of small dimension, it can be solved in polynomial time. This algorithm became a ubiquitous tool, especially in the design of parameterized algorithms for NP-complete problems, where we wish to isolate the hardness of an instance to some parameter. However, it was discovered that in many cases using Lenstra's algorithm has two drawbacks. First, the dependence of the resulting algorithms is often doubly-exponential 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 single-exponential algorithm for so called combinatorial n-fold 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 etc., 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 n-fold 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.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Parameterized complexity of distance labeling and uniform channel assignment problemsDiscrete Applied Mathematics, 2018
- Scheduling meets n-fold integer programmingJournal of Scheduling, 2017
- Graver basis and proximity techniques for block-structured separable convex integer minimization problemsMathematical Programming, 2013
- Parameterized Algorithms for Modular-Width2013
- n-Fold integer programming in cubic timeMathematical Programming, 2011
- Multivariate Complexity Analysis of Swap BriberyAlgorithmica, 2011
- Algorithmic Meta-theorems for Restrictions of TreewidthAlgorithmica, 2011
- A polynomial oracle-time algorithm for convex integer minimizationMathematical Programming, 2009
- Fixed-Parameter Algorithms for CLOSEST STRING and Related ProblemsAlgorithmica, 2003
- Integer Optimization on Convex Semialgebraic SetsDiscrete & Computational Geometry, 2000