|
|
|
|
Bounding Search Space Size via (Hyper)tree Decompositions
Lars Otten, Rina Dechter
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.
Keywords: null
Pages: 452-459
PS Link:
PDF Link: /papers/08/p452-otten.pdf
BibTex:
@INPROCEEDINGS{Otten08,
AUTHOR = "Lars Otten
and Rina Dechter",
TITLE = "Bounding Search Space Size via (Hyper)tree Decompositions",
BOOKTITLE = "Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2008",
PAGES = "452--459"
}
|
|
