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 treeNP-completenesshardness of approximationmin-sum set coverdecision-theoretic troubleshooting

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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
• Learning with attribute costs
• The SACSO methodology for troubleshooting complex systems
• The computational complexity of probabilistic inference using Bayesian belief networks
• Troubleshooting using probabilistic networks and value of information
• Troubleshooting: NP-hardness and solution methods

Cited in

(9)

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

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)