Bibliografie
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
(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