Can I read Combinatorial n-fold Integer Programming and Applications on EtoBox?

Combinatorial n-fold Integer Programming and Applications by Knop, Dušan; Koutecký, Martin; Mnich, Matthias is a scholarly article available to read on EtoBox.

What is Combinatorial n-fold Integer Programming and Applications about?

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 problemby some parameter. However, in many cases using Lenstra's algorithm has two drawbacks: First, the run time of the resulting algorithms is often doubly-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, 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, and obtain exponential speedups in the dependence on the respective parameters, the input size, or b

Author

Knop, Dušan; Koutecký, Martin; Mnich, Matthias

Published

2017

Language

EN