0381692 20240103201331.820121031235959.9 8 s. E cav_un_epca*0381691978-84-15536-57-4195-202GranadaDECSAI, University of Granada2012 Troubleshooting Bayesian networks Approximation cav_un_auth*0272969 Lín Václav Matematická teorie rozhodování Department of Decision Making Theory MTR MTR UTIA-B Department of Decision Making Theory Ústav teorie informace a automatizace AV ČR, v. v. i. http://library.utia.cas.cz/separaty/2012/MTR/lin-decision-theoretic troubleshooting hardness of approximation.pdf 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. cav_un_auth*0284378 Sixth European Workshop on Probabilistic Graphical Models Granada 19.09.2012-21.09.2012 ES 2013 BC PR RVO:67985556 http://hdl.handle.net/11104/0212105 2012 cav_un_epca*0381691 Proceedings of the Sixth European Workshop on Probabilistic Graphical Models, PGM'12 978-84-15536-57-4 195 202 Granada DECSAI, University of Granada 2012