Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
The Complexity of Approximately Solving Influence Diagrams
Denis Maua, Cassio de Campos, Marco Zaffalon
Influence diagrams allow for intuitive and yet precise description of complex situations involving decision making under uncertainty. Unfortunately, most of the problems described by influence diagrams are hard to solve. In this paper we discuss the complexity of approximately solving influence diagrams. We do not assume no-forgetting or regularity, which makes the class of problems we address very broad. Remarkably, we show that when both the tree-width and the cardinality of the variables are bounded the problem admits a fully polynomial-time approximation scheme.
Pages: 604-613
PS Link:
PDF Link: /papers/12/p604-maua.pdf
AUTHOR = "Denis Maua and Cassio de Campos and Marco Zaffalon",
TITLE = "The Complexity of Approximately Solving Influence Diagrams",
BOOKTITLE = "Proceedings of the Twenty-Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-12)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2012",
PAGES = "604--613"

hosted by DSL   •   site info   •   help