Solving Integer Quadratic Programming via Explicit and Structural Restrictions

Eduard Eiben, Robert Ganian, Dusan Knop, Sebastian Ordyniak

Research output: Contribution to conferencePaperpeer-review

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 languageEnglish
Pages1477-1484
Number of pages8
DOIs
Publication statusPublished - 17 Jul 2019
EventThe Thirty-Third AAAI Conference on Artificial Intelligence - Honolulu, United States
Duration: 27 Jan 20191 Feb 2019
https://aaai.org/Conferences/AAAI-19/

Conference

ConferenceThe Thirty-Third AAAI Conference on Artificial Intelligence
Abbreviated titleAAAI 2019
Country/TerritoryUnited States
CityHonolulu
Period27/01/191/02/19
Internet address

Cite this