Integer Programming and Incidence Treedepth

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/00216224:14330/19:00113725

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Integer Programming and Incidence Treedepth

Popis výsledku v původním jazyce

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,

Název v anglickém jazyce

Integer Programming and Incidence Treedepth

Popis výsledku anglicky

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,

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Integer Programming and Combinatorial Optimization

ISBN

978-3-030-17952-6

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

11

Strana od-do

194-204

Název nakladatele

Springer

Místo vydání

Basel

Místo konání akce

Ann Arbor

Datum konání akce

22. 5. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000493314100015