Solving Integer Quadratic Programming via Explicit and Structural Restrictions

EIBEN, Eduard, Robert GANIAN, Dusan KNOP a 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, s. 1477-1484. ISBN 978-1-57735-809-1. Dostupné z: https://dx.doi.org/10.1609/aaai.v33i01.33011477.

Základní údaje

Originální název

Solving Integer Quadratic Programming via Explicit and Structural Restrictions

Autoři

EIBEN, Eduard (703 Slovensko), Robert GANIAN (203 Česká republika, garant, domácí), Dusan KNOP (203 Česká republika) a Sebastian ORDYNIAK (276 Německo)

Vydání

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

Nakladatel

AAAI Press

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/19:00113718

Organizační jednotka

Fakulta informatiky

ISBN

978-1-57735-809-1

ISSN

DOI

http://dx.doi.org/10.1609/aaai.v33i01.33011477

UT WoS

000485292601060

Klíčová slova anglicky

Parameterized Complexity

Štítky

core_A, firank_1

---

Anotace

V originále

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.