Bibliography

Conference Paper (international conference)

Decision-theoretic troubleshooting: hardness of approximation

: Proceedings of the Sixth European Workshop on Probabilistic Graphical Models, PGM'12, p. 195-202

: Sixth European Workshop on Probabilistic Graphical Models, (Granada, ES, 19.09.2012-21.09.2012)

: Troubleshooting, Bayesian networks, Approximation

: http://library.utia.cas.cz/separaty/2012/MTR/lin-decision-theoretic troubleshooting hardness of approximation.pdf

(eng): Troubleshooting is one of the application areas of Bayesian networks. Given a probabilistic model of a malfunctioning device, the task is to find the repair strategy with minimal expected cost. Except for simple cases, finding an optimal strategy is NP-hard. We show that optimal troubleshooting strategies are also hard to approximate.

: BC