The complexity of approximating MAPs for belief networks with bounded probabilities

DOI10.1016/S0004-3702(00)00076-XzbMath0952.68137MaRDI QIDQ1589640

Stephen T. Hedetniemi, Sandra M. Hedetniemi, Ashraf M. Abdelbar

Publication date: 12 December 2000

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

complexitysatisfiabilityBayesian belief networksbipartite networkslocal variance bound

Mathematics Subject Classification ID

Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35)

Related Items (2)

Approximating MAPs for belief networks is NP-hard and other theorems ⋮ Complexity results for explanations in the structural-model approach

Cites Work

• Unnamed Item
• Unnamed Item
• Fusion, propagation, and structuring in belief networks
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Approximating MAPs for belief networks is NP-hard and other theorems
• Finding MAPs for belief networks is NP-hard
• An optimal approximation algorithm for Bayesian inference
• The computational complexity of probabilistic inference using Bayesian belief networks

This page was built for publication: The complexity of approximating MAPs for belief networks with bounded probabilities