The Complexity Landscape of Decompositional Parameters for ILP

D 2016

The Complexity Landscape of Decompositional Parameters for ILP

GANIAN, Robert a Sebastian ORDYNIAK

Základní údaje

Originální název

The Complexity Landscape of Decompositional Parameters for ILP

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí) a Sebastian ORDYNIAK (276 Německo)

Vydání

USA, Proceedings of the Thirtieth {AAAI} Conference on Artificial Intelligence, od s. 710-716, 7 s. 2016

Nakladatel

AAAI Press

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

URL

Kód RIV

RIV/00216224:14330/16:00093940

Organizační jednotka

Fakulta informatiky

ISBN

978-1-57735-760-5

Klíčová slova anglicky

ILP; treewidth

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 12. 5. 2020 19:53, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Integer Linear Programming (ILP) can be seen as the archetypical problem for NP-complete optimization problems, and a wide range of problems in artificial intelligence are solved in practice via a translation to ILP. Despite its huge range of applications, only few tractable fragments of ILP are known, probably the most prominent of which is based on the notion of total unimodularity. Using entirely different techniques, we identify new tractable fragments of ILP by studying structural parameterizations of the constraint matrix within the framework of parameterized complexity. In particular, we show that ILP is fixed-parameter tractable when parameterized by the treedepth of the constraint matrix and the maximum absolute value of any coefficient occurring in the ILP instance. Together with matching hardness results for the more general parameter treewidth, we draw a detailed complexity landscape of ILP w.r.t. decompositional parameters defined on the constraint matrix.

Citovat

GANIAN, Robert a Sebastian ORDYNIAK. The Complexity Landscape of Decompositional Parameters for ILP. Online. In Dale Schuurmans, Michael P. Wellman. Proceedings of the Thirtieth {AAAI} Conference on Artificial Intelligence. USA: AAAI Press, 2016, s. 710-716. ISBN 978-1-57735-760-5.

@inproceedings{1376002,
   author = {Ganian, Robert and Ordyniak, Sebastian},
   address = {USA},
   booktitle = {Proceedings of the Thirtieth {AAAI} Conference on Artificial Intelligence},
   editor = {Dale Schuurmans, Michael P. Wellman},
   keywords = {ILP; treewidth},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-1-57735-760-5},
   pages = {710-716},
   publisher = {AAAI Press},
   title = {The Complexity Landscape of Decompositional Parameters for ILP},
   url = {https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12432},
   year = {2016}
}

TY  - JOUR
ID  - 1376002
AU  - Ganian, Robert - Ordyniak, Sebastian
PY  - 2016
TI  - The Complexity Landscape of Decompositional Parameters for ILP
PB  - AAAI Press
CY  - USA
SN  - 9781577357605
KW  - ILP
KW  - treewidth
UR  - https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12432
N2  - Integer Linear Programming (ILP) can be seen as the archetypical problem for NP-complete optimization problems, and a wide range of problems in artificial intelligence are solved in practice via a translation to ILP. Despite its huge range of applications, only few tractable fragments of ILP are known, probably the most prominent of which is based on the notion of total unimodularity. Using entirely different techniques, we identify new tractable fragments of ILP by studying structural parameterizations of the constraint matrix within the framework of parameterized complexity. In particular, we show that ILP is fixed-parameter tractable when parameterized by the treedepth of the constraint matrix and the maximum absolute value of any coefficient occurring in the ILP instance. Together with matching hardness results for the more general parameter treewidth, we draw a detailed complexity landscape of ILP w.r.t. decompositional parameters defined on the constraint matrix.
ER  -

GANIAN, Robert a Sebastian ORDYNIAK. The Complexity Landscape of Decompositional Parameters for ILP. Online. In Dale Schuurmans, Michael P. Wellman. \textit{Proceedings of the Thirtieth $\{$AAAI$\}$ Conference on Artificial Intelligence}. USA: AAAI Press, 2016, s.~710-716. ISBN~978-1-57735-760-5.

Podrobný výpis o publikaci