EIBEN, Eduard, Robert GANIAN, Dusan KNOP, Sebastian ORDYNIAK, Michal PILIPCZUK and Marcin WROCHNA. Integer Programming and Incidence Treedepth. Online. In Andrea Lodi and Viswanath Nagarajan. Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019. USA: Springer, 2019, p. 194-204. ISBN 978-3-030-17952-6. Available from: https://dx.doi.org/10.1007/978-3-030-17953-3_15.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Integer Programming and Incidence Treedepth
Authors EIBEN, Eduard (703 Slovakia), Robert GANIAN (203 Czech Republic, guarantor, belonging to the institution), Dusan KNOP (203 Czech Republic), Sebastian ORDYNIAK (276 Germany), Michal PILIPCZUK (616 Poland) and Marcin WROCHNA (616 Poland).
Edition USA, Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, p. 194-204, 11 pp. 2019.
Publisher Springer
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
WWW URL
Impact factor Impact factor: 0.402 in 2005
RIV identification code RIV/00216224:14330/19:00113725
Organization unit Faculty of Informatics
ISBN 978-3-030-17952-6
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-030-17953-3_15
UT WoS 000493314100015
Keywords in English Parameterized Complexity
Tags core_A, firank_A
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 14/5/2020 10:54.
Abstract
Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matrix on the other side. To that end, integer linear programming is fixed-parameter tractable with respect to the primal (or dual) treedepth of the Gaifman graph of its constraint matrix and the largest coefficient (in absolute value). Motivated by this, Koutecký, Levin, and Onn [ICALP 2018] asked whether it is possible to extend these result to a more broader class of integer linear programs. More formally, is integer linear programming fixed-parameter tractable with respect to the incidence treedepth of its constraint matrix and the largest coefficient (in absolute value)? We answer this question in negative.
PrintDisplayed: 26/4/2024 13:24