Bounding Search Space Size via (Hyper)tree Decompositions
Abstract
This paper develops a measure for bounding the performance of AND/OR search algorithms for solving a variety of queries over graphical models. We show how drawing a connection to the recent notion of hypertree decompositions allows to exploit determinism in the problem specification and produce tighter bounds. We demonstrate on a variety of practical problem instances that we are often able to improve upon existing bounds by several orders of magnitude.
Cite
Text
Otten and Dechter. "Bounding Search Space Size via (Hyper)tree Decompositions." Conference on Uncertainty in Artificial Intelligence, 2008.Markdown
[Otten and Dechter. "Bounding Search Space Size via (Hyper)tree Decompositions." Conference on Uncertainty in Artificial Intelligence, 2008.](https://mlanthology.org/uai/2008/otten2008uai-bounding/)BibTeX
@inproceedings{otten2008uai-bounding,
title = {{Bounding Search Space Size via (Hyper)tree Decompositions}},
author = {Otten, Lars and Dechter, Rina},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {2008},
pages = {452-459},
url = {https://mlanthology.org/uai/2008/otten2008uai-bounding/}
}