J 2019

Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey

GANIAN, Robert a Sebastian ORDYNIAK

Základní údaje

Originální název

Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí) a Sebastian ORDYNIAK (276 Německo)

Vydání

Algorithms, 2019, 1999-4893

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Kód RIV

RIV/00216224:14330/19:00113717

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000505741500004

Klíčová slova anglicky

Parameterized Complexity
Změněno: 14. 5. 2020 10:41, Mgr. Michal Petr

Anotace

V originále

Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a detailed complexity landscape for the problem centered around the structure of graphical representations of instances. The aim of this survey is to summarize these recent developments, put them into context and a unified format, and make them more approachable for experts from many diverse backgrounds.