Solving Integer Quadratic Programming via Explicit and Structural Restrictions. / Eiben, Eduard; Ganian, Robert; Knop, Dusan; Ordyniak, Sebastian.
2019. 1477-1484 Paper presented at The Thirty-Third AAAI Conference on Artificial Intelligence, Honolulu, United States.Research output: Contribution to conference › Paper › peer-review
Published
Abstract
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.
| Original language | English |
|---|---|
| Pages | 1477-1484 |
| Number of pages | 8 |
| DOIs | |
| Publication status | Published - 17 Jul 2019 |
| Event | The Thirty-Third AAAI Conference on Artificial Intelligence - Honolulu, United States Duration: 27 Jan 2019 → 1 Feb 2019 https://aaai.org/Conferences/AAAI-19/ |
Conference
| Conference | The Thirty-Third AAAI Conference on Artificial Intelligence |
|---|---|
| Abbreviated title | AAAI 2019 |
| Country | United States |
| City | Honolulu |
| Period | 27/01/19 → 1/02/19 |
| Internet address |
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.
ID: 34924551