[Back]


Talks and Poster Presentations (with Proceedings-Entry):

B. Bliem, B. Kaufmann, T. Schaub, S. Woltran:
"ASP for Anytime Dynamic Programming on Tree Decompositions (Extended Abstract)";
Talk: Annual German Conference on Artificial Intelligence (KI), Klagenfurt, Austria; 2016-09-26 - 2016-09-30; in: "KI 2016: Advances in Artificial Intelligence", G. Friedrich, M. Helmert, F. Wotawa (ed.); LNCS/Springer, 9904 (2016), ISBN: 978-3-319-46072-7; 257 - 263.



English abstract:
Answer Set Programming (ASP) has recently been employed to specify and run dynamic programming (DP) algorithms on tree decompositions, a central approach in the field of parameterized complexity, which aims at solving hard problems efficiently for instances of certain structure. This ASP-based method followed the standard DP approach where tables are computed in a bottom-up fashion, yielding good results for several counting or enumeration problems. However, for optimization problems this approach lacks the possibility to report solutions before the optimum is found, and for search problems it often computes a lot of unnecessary rows. In this paper, we present a novel ASP-based system allowing for "lazy" DP, which utilizes recent multishot ASP technology. Preliminary experimental results show that this approach not only yields better performance for search problems, but also outperforms some state-of-the-art ASP encodings for optimization problems in terms of anytime computation, i.e., measuring the quality of the best solution after a certain timeout.


Related Projects:
Project Head Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Project Head Stefan Woltran:
START


Created from the Publication Database of the Vienna University of Technology.