Decision-theoretic troubleshooting: hardness of approximation

DOI10.1016/J.IJAR.2013.07.003MaRDI QIDQ2440184zbMATH OpenOpenAlexFDO

Authors Václav Lín

Publication date 27 March 2014

Published in International Journal of Approximate Reasoning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.6551

zbMATH Keywords

decision treedecision-theoretic troubleshootinghardness of approximationmin-sum set coverNP-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Reasoning under uncertainty in the context of artificial intelligence (68T37)

Abstract: 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.

Recommendations

• Troubleshooting: NP-hardness and solution methods
• Complexity of decision-theoretic troubleshooting
• Scheduling results applicable to decision-theoretic troubleshooting
• Extensions of Decision-Theoretic Troubleshooting: Cost Clusters and Precedence Constraints
• Troubleshooting using probabilistic networks and value of information

Cites work

• Approximating min sum set cover
• Complexity of decision-theoretic troubleshooting
• Computational Complexity
• Constructing optimal binary decision trees is NP-complete
• Database Theory - ICDT 2005
• Decision trees for entity identification, approximation algorithms and hardness results
• Extensions of Decision-Theoretic Troubleshooting: Cost Clusters and Precedence Constraints
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Learning with attribute costs
• The computational complexity of probabilistic inference using Bayesian belief networks
• The SACSO methodology for troubleshooting complex systems
• Troubleshooting using probabilistic networks and value of information
• Troubleshooting: NP-hardness and solution methods

Cited in

(9)

• Troubleshooting using probabilistic networks and value of information
• Troubleshooting: NP-hardness and solution methods
• Extensions of Decision-Theoretic Troubleshooting: Cost Clusters and Precedence Constraints
• Complexity of decision-theoretic troubleshooting
• scientific article; zbMATH DE number 1538017 (Why is no real title available?)
• Scheduling results applicable to decision-theoretic troubleshooting
• scientific article; zbMATH DE number 1844466 (Why is no real title available?)
• About the choice of the variable to unassign in a decision repair algorithm
• The hardness of the expected decision depth problem

This page was built for publication: Decision-theoretic troubleshooting: hardness of approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2440184)