GANIAN, Robert and Sebastian ORDYNIAK. Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey. Algorithms. 2019, vol. 12, No 12, p. 1-14. ISSN 1999-4893. Available from: https://dx.doi.org/10.3390/A12120248.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
Authors GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution) and Sebastian ORDYNIAK (276 Germany).
Edition Algorithms, 2019, 1999-4893.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Switzerland
Confidentiality degree is not subject to a state or trade secret
WWW URL
RIV identification code RIV/00216224:14330/19:00113717
Organization unit Faculty of Informatics
Doi http://dx.doi.org/10.3390/A12120248
UT WoS 000505741500004
Keywords in English Parameterized Complexity
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 14/5/2020 10:41.
Abstract
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.
PrintDisplayed: 1/8/2024 12:20