D 2019

Integer Programming and Incidence Treedepth

EIBEN, Eduard, Robert GANIAN, Dusan KNOP, Sebastian ORDYNIAK, Michal PILIPCZUK et. al.

Základní údaje

Originální název

Integer Programming and Incidence Treedepth

Autoři

EIBEN, Eduard (703 Slovensko), Robert GANIAN (203 Česká republika, garant, domácí), Dusan KNOP (203 Česká republika), Sebastian ORDYNIAK (276 Německo), Michal PILIPCZUK (616 Polsko) a Marcin WROCHNA (616 Polsko)

Vydání

USA, Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, od s. 194-204, 11 s. 2019

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/19:00113725

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-17952-6

ISSN

DOI

UT WoS

000493314100015

Klíčová slova anglicky

Parameterized Complexity

Štítky

Změněno: 14. 5. 2020 10:54, Mgr. Michal Petr

Anotace

V originále

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.