The Complexity of Approximately Solving Influence Diagrams

Denis D. Maua, Cassio Polpo de Campos, Marco Zaffalon
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:602-611, 2012.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-maua12a, title = {The Complexity of Approximately Solving Influence Diagrams}, author = {Maua, Denis D. and de Campos, Cassio Polpo and Zaffalon, Marco}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {602--611}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/maua12a/maua12a.pdf}, url = {https://proceedings.mlr.press/r10/maua12a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T The Complexity of Approximately Solving Influence Diagrams %A Denis D. Maua %A Cassio Polpo de Campos %A Marco Zaffalon %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-maua12a %I PMLR %P 602--611 %U https://proceedings.mlr.press/r10/maua12a.html %V R10 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Maua, D.D., de Campos, C.P. & Zaffalon, M.. (2012). The Complexity of Approximately Solving Influence Diagrams. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:602-611 Available from https://proceedings.mlr.press/r10/maua12a.html. Reissued by PMLR on 04 October 2026.

Related Material