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://dx.doi.org/10.1609/aaai.v33i01.33011477.
Other formats:   BibTeX LaTeX RIS
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
Original 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
WWW URL
RIV identification code RIV/00216224:14330/19:00113718
Organization unit Faculty of Informatics
ISBN 978-1-57735-809-1
ISSN 2159-5399
Doi http://dx.doi.org/10.1609/aaai.v33i01.33011477
UT WoS 000485292601060
Keywords in English Parameterized Complexity
Tags core_A, firank_1
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 14/5/2020 10:42.
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.
PrintDisplayed: 18/8/2024 00:44