2013/04/24 by Václav Ĺın, Lín, Václav
Computer Science · Decision Sciences · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Risk and Safety Analysis #Software Reliability and Analysis Research
paper · pdf · doi:10.48550/arxiv.1304.6551
openalex publication_date 2013/04/24 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
Decision-theoretic troubleshooting is one of the areas to which Bayesian networks can be applied. Given a probabilistic model of a malfunctioning man-made device, the task is to construct a repair strategy with minimal expected cost. The problem has received considerable attention over the past two decades. Efficient solution algorithms have been found for simple cases, whereas other variants have been proven NP-complete. We study several variants of the problem found in literature, and prove that computing approximate troubleshooting strategies is NP-hard. In the proofs, we exploit a close connection to set-covering problems.