Publication details

Solving Integer Quadratic Programming via Explicit and Structural Restrictions

Authors

EIBEN Eduard GANIAN Robert KNOP Dusan ORDYNIAK Sebastian

Type Article in Proceedings
Conference Proceedings of the AAAI Conference on Artificial Intelligence
MU Faculty or unit

Faculty of Informatics

Citation
Web https://aaai.org/ojs/index.php/AAAI/article/view/3960
Doi http://dx.doi.org/10.1609/aaai.v33i01.33011477
Keywords Parameterized Complexity
Description 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.