The Complexity of Approximately Solving Influence Diagrams

2012/10/16 by Denis D. Maua, Maua, Denis D., Cassio Polpo de Campos +3
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #cs.AI

paper · pdf · doi:10.48550/arxiv.1210.4890

Appears in Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence (UAI2012)

arxiv created 2012/10/16 · arxiv updated 2012/10/19

Abstract

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.

Related

• Solving Limited Memory Influence Diagrams
• Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search
• Solving influence diagrams via efficient mixed-integer programming formulations and heuristics
• Solving Influence Diagrams using HUGIN, Shafer-Shenoy and Lazy Propagation
• A symbolic algebra for the computation of expected utilities in multiplicative influence diagrams