Search
 
loader loading subjects...
cover
Choosing the Root of the Tree Decomposition When Solving WCSPs: Preliminary Results
Aleksandra Petrova, Javier Larrosa, Emma Rollon
56 - 65
10.3233/FAIA210116
Research Article
Frontiers in Artificial Intelligence and Applications
Volume 339: Artificial Intelligence Research and Development
Abstract

In this paper we analyze the effect of selecting the root in a tree decomposition when using decomposition-based backtracking algorithms. We focus on optimization tasks for Graphical Models using the BTD algorithm. We show that the choice of the root typically has a dramatic effect in the solving performance. Then we investigate different simple measures to predict near optimal roots. Our study shows that correlations are often low, so the automatic selection of a near optimal root will require more sophisticated techniques.

Download
Creative Commons License