Integer Programming and Incidence Treedepth
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F19%3A00331346" target="_blank" >RIV/68407700:21240/19:00331346 - isvavai.cz</a>
Alternative codes found
RIV/00216224:14330/19:00113725
Result on the web
<a href="https://link.springer.com/chapter/10.1007%2F978-3-030-17953-3_15" target="_blank" >https://link.springer.com/chapter/10.1007%2F978-3-030-17953-3_15</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-17953-3_15" target="_blank" >10.1007/978-3-030-17953-3_15</a>
Alternative languages
Result language
angličtina
Original language name
Integer Programming and Incidence Treedepth
Original language description
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. We prove that deciding the feasibility of a system in the standard form,
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Integer Programming and Combinatorial Optimization
ISBN
978-3-030-17952-6
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
11
Pages from-to
194-204
Publisher name
Springer
Place of publication
Basel
Event location
Ann Arbor
Event date
May 22, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000493314100015