Integer Programming and Incidence Treedepth

D 2019

Integer Programming and Incidence Treedepth

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

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

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

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

Publication form

electronic version available online

References:

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

DOI

http://dx.doi.org/10.1007/978-3-030-17953-3_15

UT WoS

000493314100015

Keywords in English

Parameterized Complexity

Abstract

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.

Citovat

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.

@inproceedings{1648276,
   author = {Eiben, Eduard and Ganian, Robert and Knop, Dusan and Ordyniak, Sebastian and Pilipczuk, Michal and Wrochna, Marcin},
   address = {USA},
   booktitle = {Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019},
   doi = {http://dx.doi.org/10.1007/978-3-030-17953-3_15},
   editor = {Andrea Lodi and Viswanath Nagarajan},
   keywords = {Parameterized Complexity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-3-030-17952-6},
   pages = {194-204},
   publisher = {Springer},
   title = {Integer Programming and Incidence Treedepth},
   url = {https://link.springer.com/chapter/10.1007%2F978-3-030-17953-3_15},
   year = {2019}
}

TY  - JOUR
ID  - 1648276
AU  - Eiben, Eduard - Ganian, Robert - Knop, Dusan - Ordyniak, Sebastian - Pilipczuk, Michal - Wrochna, Marcin
PY  - 2019
TI  - Integer Programming and Incidence Treedepth
PB  - Springer
CY  - USA
SN  - 9783030179526
KW  - Parameterized Complexity
UR  - https://link.springer.com/chapter/10.1007%2F978-3-030-17953-3_15
L2  - https://link.springer.com/chapter/10.1007%2F978-3-030-17953-3_15
N2  - 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.
ER  -

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. \textit{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.

Detailed Information on Publication Record