Decision-theoretic troubleshooting: hardness of approximation
1.
SYSNO ASEP
0381692
Document Type
C - Proceedings Paper (int. conf.)
R&D Document Type
Conference Paper
Title
Decision-theoretic troubleshooting: hardness of approximation
Author(s)
Lín, Václav (UTIA-B)
Source Title
Proceedings of the Sixth European Workshop on Probabilistic Graphical Models, PGM'12. - Granada : DECSAI, University of Granada, 2012
- ISBN 978-84-15536-57-4
Pages
s. 195-202
Number of pages
8 s.
Publication form
Online - E
Action
Sixth European Workshop on Probabilistic Graphical Models
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.
