Unary Integer Linear Programming with Structural Restrictions

D 2018

Unary Integer Linear Programming with Structural Restrictions

EIBEN, Eduard, Robert GANIAN, Dusan KNOP a Sebastian ORDYNIAK

Základní údaje

Originální název

Unary Integer Linear Programming with Structural Restrictions

Autoři

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

Vydání

USA, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, od s. 1284-1290, 7 s. 2018

Nakladatel

ijcai.org

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"

Kód RIV

RIV/00216224:14330/18:00106814

Organizační jednotka

Fakulta informatiky

ISBN

978-0-9992411-2-7

ISSN

DOI

http://dx.doi.org/10.24963/ijcai.2018/179

UT WoS

000764175401059

Klíčová slova anglicky

Integer Linear Programming; Classical Complexity

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 18. 5. 2022 10:34, Mgr. Michal Petr

Anotace

V originále

Recently a number of algorithmic results have appeared which show the tractability of Integer Linear Programming (ILP) instances under strong restrictions on variable domains and/or coefficients (AAAI 2016, AAAI 2017, IJCAI 2017). In this paper, we target ILPs where neither the variable domains nor the coefficients are restricted by a fixed constant or parameter; instead, we only require that our instances can be encoded in unary. We provide new algorithms and lower bounds for such ILPs by exploiting the structure of their variable interactions, represented as a graph. Our first set of results focuses on solving ILP instances through the use of a graph parameter called clique-width, which can be seen as an extension of treewidth which also captures well-structured dense graphs. In particular, we obtain a polynomial-time algorithm for instances of bounded clique-width whose domain and coefficients are polynomially bounded by the input size, and we complement this positive result by a number of algorithmic lower bounds. Afterwards, we turn our attention to ILPs with acyclic variable interactions. In this setting, we obtain a complexity map for the problem with respect to the graph representation used and restrictions on the encoding.

Citovat

EIBEN, Eduard, Robert GANIAN, Dusan KNOP a Sebastian ORDYNIAK. Unary Integer Linear Programming with Structural Restrictions. Online. In Jerome Lang. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. USA: ijcai.org, 2018, s. 1284-1290. ISBN 978-0-9992411-2-7. Dostupné z: https://dx.doi.org/10.24963/ijcai.2018/179.

@inproceedings{1523777,
   author = {Eiben, Eduard and Ganian, Robert and Knop, Dusan and Ordyniak, Sebastian},
   address = {USA},
   booktitle = {Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence},
   doi = {http://dx.doi.org/10.24963/ijcai.2018/179},
   editor = {Jerome Lang},
   keywords = {Integer Linear Programming; Classical Complexity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-0-9992411-2-7},
   pages = {1284-1290},
   publisher = {ijcai.org},
   title = {Unary Integer Linear Programming with Structural Restrictions},
   year = {2018}
}

TY  - JOUR
ID  - 1523777
AU  - Eiben, Eduard - Ganian, Robert - Knop, Dusan - Ordyniak, Sebastian
PY  - 2018
TI  - Unary Integer Linear Programming with Structural Restrictions
PB  - ijcai.org
CY  - USA
SN  - 9780999241127
KW  - Integer Linear Programming
KW  - Classical Complexity
N2  - Recently a number of algorithmic results have appeared which show the tractability of Integer Linear Programming (ILP) instances under strong restrictions on variable domains and/or coefficients (AAAI 2016, AAAI 2017, IJCAI 2017). In this paper, we target ILPs where neither the variable domains nor the coefficients are restricted by a fixed constant or parameter; instead, we only require that our instances can be encoded in unary. We provide new algorithms and lower bounds for such ILPs by exploiting the structure of their variable interactions, represented as a graph. Our first set of results focuses on solving ILP instances through the use of a graph parameter called clique-width, which can be seen as an extension of treewidth which also captures well-structured dense graphs. In particular, we obtain a polynomial-time algorithm for instances of bounded clique-width whose domain and coefficients are polynomially bounded by the input size, and we complement this positive result by a number of algorithmic lower bounds. Afterwards, we turn our attention to ILPs with acyclic variable interactions. In this setting, we obtain a complexity map for the problem with respect to the graph representation used and restrictions on the encoding.
ER  -

EIBEN, Eduard, Robert GANIAN, Dusan KNOP a Sebastian ORDYNIAK. Unary Integer Linear Programming with Structural Restrictions. Online. In Jerome Lang. \textit{Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence}. USA: ijcai.org, 2018, s.~1284-1290. ISBN~978-0-9992411-2-7. Dostupné z: https://dx.doi.org/10.24963/ijcai.2018/179.

Podrobný výpis o publikaci