EIBEN, Eduard, Robert GANIAN, Dusan KNOP and Sebastian ORDYNIAK. Unary Integer Linear Programming with Structural Restrictions. In Jerome Lang. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. USA: ijcai.org. p. 1284-1290. ISBN 978-0-9992411-2-7. doi:10.24963/ijcai.2018/179. 2018.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Unary Integer Linear Programming with Structural Restrictions
Authors EIBEN, Eduard (703 Slovakia), Robert GANIAN (203 Czech Republic, guarantor, belonging to the institution), Dusan KNOP (203 Czech Republic) and Sebastian ORDYNIAK (276 Germany).
Edition USA, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, p. 1284-1290, 7 pp. 2018.
Publisher ijcai.org
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
RIV identification code RIV/00216224:14330/18:00106814
Organization unit Faculty of Informatics
ISBN 978-0-9992411-2-7
ISSN 1045-0823
Doi http://dx.doi.org/10.24963/ijcai.2018/179
UT WoS 000764175401059
Keywords in English Integer Linear Programming; Classical Complexity
Tags core_A, firank_1
Tags International impact, Reviewed
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 18/5/2022 10:34.
Abstract
Recently a number of algorithmic results have appeared which show the tractability of Integer Linear Programming (ILP) instances under strong restrictions on variable domains and/or coefficients (AAAI 2016, AAAI 2017, IJCAI 2017). In this paper, we target ILPs where neither the variable domains nor the coefficients are restricted by a fixed constant or parameter; instead, we only require that our instances can be encoded in unary. We provide new algorithms and lower bounds for such ILPs by exploiting the structure of their variable interactions, represented as a graph. Our first set of results focuses on solving ILP instances through the use of a graph parameter called clique-width, which can be seen as an extension of treewidth which also captures well-structured dense graphs. In particular, we obtain a polynomial-time algorithm for instances of bounded clique-width whose domain and coefficients are polynomially bounded by the input size, and we complement this positive result by a number of algorithmic lower bounds. Afterwards, we turn our attention to ILPs with acyclic variable interactions. In this setting, we obtain a complexity map for the problem with respect to the graph representation used and restrictions on the encoding.
PrintDisplayed: 19/4/2024 03:22