Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Phase Transition of Tractability in Constraint Satisfaction and Bayesian Network Inference
Yong Gao
Abstract:
There has been great interest in identifying tractable subclasses of NP complete problems and designing efficient algorithms for these tractable classes. Constraint satisfaction and Bayesian network inference are two examples of such problems that are of great importance in AI and algorithms. In this paper we study, under the frameworks of random constraint satisfaction problems and random Bayesian networks, a typical tractable subclass characterized by the treewidth of the problems. We show that the property of having a bounded treewidth for CSPs and Bayesian network inference problem has a phase transition that occurs while the underlying structures of problems are still sparse. This implies that algorithms making use of treewidth based structural knowledge only work efficiently in a limited range of random instance
Keywords:
Pages: 265-271
PS Link:
PDF Link: /papers/03/p265-gao.pdf
BibTex:
@INPROCEEDINGS{Gao03,
AUTHOR = "Yong Gao ",
TITLE = "Phase Transition of Tractability in Constraint Satisfaction and Bayesian Network Inference",
BOOKTITLE = "Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2003",
PAGES = "265--271"
}


hosted by DSL   •   site info   •   help