Decision-theoretic troubleshooting: hardness of approximation

DOI10.1016/j.ijar.2013.07.003zbMath1390.68667arXiv1304.6551MaRDI QIDQ2440184

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

NP-completeness; decision tree; hardness of approximation; min-sum set cover; decision-theoretic troubleshooting

Mathematics Subject Classification ID

68T37: Reasoning under uncertainty in the context of artificial intelligence

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Scheduling results applicable to decision-theoretic troubleshooting

Cites Work

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