The Complexity of Approximately Solving Influence Diagrams

D. D. Mauá, C. P. de Campos, M. Zaffalon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Citations (Scopus)

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 treewidth and the cardinality of the variables are bounded the problem admits a fully polynomial-time approximation scheme.
Original languageEnglish
Title of host publicationConference on Uncertainty in Artificial Intelligence (UAI)
PublisherAUAI Press
Pages604-613
Number of pages10
Publication statusPublished - 2012

Bibliographical note

(acc.rate 31%, double-blind peer reviewed by >3 reviewers)

Fingerprint Dive into the research topics of 'The Complexity of Approximately Solving Influence Diagrams'. Together they form a unique fingerprint.

  • Cite this

    Mauá, D. D., de Campos, C. P., & Zaffalon, M. (2012). The Complexity of Approximately Solving Influence Diagrams. In Conference on Uncertainty in Artificial Intelligence (UAI) (pp. 604-613). AUAI Press. http://www.eeecs.qub.ac.uk/~c.decampos/publist/papers/maua2012b.pdf