Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
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"
}


hosted by DSL   •   site info   •   help