Decision-theoretic troubleshooting: hardness of approximation

DOI10.1016/J.IJAR.2013.07.003zbMATH Open1390.68667arXiv1304.6551OpenAlexW2104625216MaRDI QIDQ2440184FDOQ2440184

Authors: Václav Lín 

Publication date: 27 March 2014

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

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.

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

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

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)

Cites Work

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

Cited In (9)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)