Solving Integer Quadratic Programming via Explicit and
Structural Restrictions

D 2019

Solving Integer Quadratic Programming via Explicit and Structural Restrictions

EIBEN, Eduard; Robert GANIAN; Dusan KNOP and Sebastian ORDYNIAK

Basic information

Original name

Solving Integer Quadratic Programming via Explicit and Structural Restrictions

Authors

EIBEN, Eduard (703 Slovakia); Robert GANIAN (203 Czech Republic, guarantor, belonging to the institution); Dusan KNOP (203 Czech Republic) and Sebastian ORDYNIAK (276 Germany)

Edition

USA, Proceedings of the AAAI Conference on Artificial Intelligence, p. 1477-1484, 8 pp. 2019

Publisher

AAAI Press

Other information

Language

English

Type of outcome

Proceedings paper

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

is not subject to a state or trade secret

Publication form

electronic version available online

References:

URL

RIV identification code

RIV/00216224:14330/19:00113718

Organization unit

Faculty of Informatics

ISBN

978-1-57735-809-1

ISSN

DOI

https://doi.org/10.1609/aaai.v33i01.33011477

UT WoS

000485292601060

EID Scopus

2-s2.0-85090807031

Keywords in English

Parameterized Complexity

Abstract

In the original language

We study the parameterized complexity of Integer Quadratic Programming under two kinds of restrictions: explicit restrictions on the domain or coefficients, and structural restrictions on variable interactions. We argue that both kinds of restrictions are necessary to achieve tractability for Integer Quadratic Programming, and obtain four new algorithms for the problem that are tuned to possible explicit restrictions of instances that we may wish to solve. The presented algorithms are exact, deterministic, and complemented by appropriate lower bounds.

Cite

EIBEN, Eduard; Robert GANIAN; Dusan KNOP and Sebastian ORDYNIAK. Solving Integer Quadratic Programming via Explicit and Structural Restrictions. Online. In Peter Stone. Proceedings of the AAAI Conference on Artificial Intelligence. USA: AAAI Press, 2019, p. 1477-1484. ISBN 978-1-57735-809-1. Available from: https://doi.org/10.1609/aaai.v33i01.33011477.

@inproceedings{1648250,
   author = {Eiben, Eduard and Ganian, Robert and Knop, Dusan and Ordyniak, Sebastian},
   address = {USA},
   booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence},
   doi = {https://doi.org/10.1609/aaai.v33i01.33011477},
   editor = {Peter Stone},
   keywords = {Parameterized Complexity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-1-57735-809-1},
   pages = {1477-1484},
   publisher = {AAAI Press},
   title = {Solving Integer Quadratic Programming via Explicit and Structural Restrictions},
   url = {https://aaai.org/ojs/index.php/AAAI/article/view/3960},
   year = {2019}
}

TY  - CONF
ID  - 1648250
AU  - Eiben, Eduard - Ganian, Robert - Knop, Dusan - Ordyniak, Sebastian
PY  - 2019
TI  - Solving Integer Quadratic Programming via Explicit and Structural Restrictions
PB  - AAAI Press
CY  - USA
SN  - 9781577358091
KW  - Parameterized Complexity
UR  - https://aaai.org/ojs/index.php/AAAI/article/view/3960
L2  - https://aaai.org/ojs/index.php/AAAI/article/view/3960
N2  - We study the parameterized complexity of Integer Quadratic Programming under two kinds of restrictions: explicit restrictions on the domain or coefficients, and structural restrictions on variable interactions. We argue that both kinds of restrictions are necessary to achieve tractability for Integer Quadratic Programming, and obtain four new algorithms for the problem that are tuned to possible explicit restrictions of instances that we may wish to solve. The presented algorithms are exact, deterministic, and complemented by appropriate lower bounds.
ER  -

EIBEN, Eduard; Robert GANIAN; Dusan KNOP and Sebastian ORDYNIAK. Solving Integer Quadratic Programming via Explicit and Structural Restrictions. Online. In Peter Stone. \textit{Proceedings of the AAAI Conference on Artificial Intelligence}. USA: AAAI Press, 2019, p.~1477-1484. ISBN~978-1-57735-809-1. Available from: https://doi.org/10.1609/aaai.v33i01.33011477.

Přehled o publikaci