Combinatorial n -fold integer programming and applications
- PDF / 598,522 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 66 Downloads / 235 Views
Series A
Combinatorial n-fold integer programming and applications Dušan Knop1
· Martin Koutecký2,3 · Matthias Mnich4,5
Received: 27 October 2017 / Accepted: 8 May 2019 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2019
Abstract Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the program, and polynomial in the size of the ILP. That algorithm became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra’s algorithm has two drawbacks: First, the run time of the resulting algorithms is often double-exponential in the parameter, and second, an ILP formulation in small dimension cannot easily express problems involving many different costs. Inspired by the work of Hemmecke et al. (Math Program 137(1– 2, Ser. A):325–341, 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 many relevant problems problems like Closest String, Swap Bribery, Weighted Set Multicover, and several others, 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, existence of an augmenting step implies 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 Integer programming · Augmentation algorithm · Closest string · Fixed-parameter algorithms
ˇ GA UK Grant Project 1784214, Research supported by CE-ITI Grant Project P202/12/G061 of GA CR, ERC Starting Grant 306465 (BeyondWorstCase), DFG Grant MN 59/4-1, Israel Science Foundation Grant 308/18, and Charles University project UNCE/SCI/004. An extended abstract of these results appeared in the Proceedings of the 25th European Symposium on Algorithms [45]. Extended author information available on the last page of the article
123
D. Knop et al.
Mathematics Subject Classification 90C10 · 90C27 · 90C39
1 Introduction The Integer Linear Programming (ILP) problem is fundamental as it models many combinatorial optimization problems. Since it is NP-complete, we naturally ask about the complexity of special cases. A fundamental algorithm by Lenstra from 1983 shows that ILPs can be solved in polynomial time when their number of variables (the dimension) d is fixed [52]; that algorithm is thus a natural tool to prove that the complexi
Data Loading...
