The Complexity of Approximately Solving Influence Diagrams
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.
Cite
Text
Mauá et al. "The Complexity of Approximately Solving Influence Diagrams." Conference on Uncertainty in Artificial Intelligence, 2012.Markdown
[Mauá et al. "The Complexity of Approximately Solving Influence Diagrams." Conference on Uncertainty in Artificial Intelligence, 2012.](https://mlanthology.org/uai/2012/maua2012uai-complexity/)BibTeX
@inproceedings{maua2012uai-complexity,
title = {{The Complexity of Approximately Solving Influence Diagrams}},
author = {Mauá, Denis Deratani and de Campos, Cassio Polpo and Zaffalon, Marco},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {2012},
pages = {604-613},
url = {https://mlanthology.org/uai/2012/maua2012uai-complexity/}
}