Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Kronegger, A. Pfandler, S. Ordyniak:
"Variable-Deletion Backdoors to Planning";
Poster: Twenty-Ninth AAAI Conference on Artificial Intelligence,
Austin, Texas, USA;
25.01.2015
- 30.01.2015; in: "Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA",
B. Bonet, S. Koenig (Hrg.);
AAAI Press,
(2015),
S. 3305
- 3312.
Kurzfassung englisch:
Backdoors are a powerful tool to obtain efficient algorithms for hard problems. Recently, two new notions of backdoors to planning were introduced. However, for one of the new notions (i.e., variable-deletion) only hardness results are known so far. In this work we improve the situation by defining a new type of variable-deletion backdoors based on the extended causal graph of a planning instance. For this notion of backdoors several fixed-parameter tractable algorithms are identified. Furthermore, we explore the capabilities of polynomial time preprocessing, i.e., we check whether there exists a polynomial kernel. Our results also show the close connection between planning and verification problems such as Vector Addition System with States (VASS).
Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.