[Back]


Scientific Reports:

B. Bliem, G. Charwat, M. Hecher, S. Woltran:
"D-FLAT^2: Subset Minimization in Dynamic Programming on Tree Decompositions Made Easy";
Report for TU Wien; Report No. DBAI-TR-2015-93, 2015; 38 pages.



English abstract:
Many problems from the area of AI have been shown tractable for bounded treewidth. In order to put such results into practice, quite involved dynamic programming (DP) algorithms on tree decompositions have to be designed and implemented. These algorithms typically show recurring patterns that call for tasks like subset minimization. In this paper we present a novel approach to obtain such DP algorithms from simpler principles, where the DP formalization of subset minimization is performed automatically. We first give a theoretical account of our novel method, and then present D-FLAT^2, a system that allows one to specify the core DP algorithm via answer set programming (ASP). We illustrate the approach at work by providing several DP algorithms that are more space-efficient than existing solutions, while featuring improved readability, reuse and therefore maintainability of ASP code. Experiments show that our approach also yields a significant improvement in runtime performance.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_243899.pdf



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.