The Complexity of Approximately Solving Influence Diagrams
  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.
