Combinatorial n-fold integer programming and applications

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10403784" target="_blank" >RIV/00216208:11320/19:10403784 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21240/20:00343438

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=OLaDV9455S" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=OLaDV9455S</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10107-019-01402-2" target="_blank" >10.1007/s10107-019-01402-2</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Combinatorial n-fold integer programming and applications

Popis výsledku v původním jazyce

Many fundamental ????????-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 ????????-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra&apos;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 combinatorialn-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&apos;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 &quot;local&quot; 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.

Název v anglickém jazyce

Combinatorial n-fold integer programming and applications

Popis výsledku anglicky

Many fundamental ????????-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 ????????-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra&apos;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 combinatorialn-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&apos;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 &quot;local&quot; 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Mathematical Programming, Series A

ISSN

0025-5610

e-ISSN

—

Svazek periodika

2020

Číslo periodika v rámci svazku

184

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

34

Strana od-do

1-34

Kód UT WoS článku

000574702000002

EID výsledku v databázi Scopus

2-s2.0-85075419122