The complexity of approximating MAPs for belief networks with bounded probabilities

DOI10.1016/S0004-3702(00)00076-XMaRDI QIDQ1589640zbMATH OpenFDO

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

Publication date 12 December 2000

Published in Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

complexitysatisfiabilitybipartite networksBayesian belief networkslocal variance bound

Mathematics Subject Classification ID

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

Recommendations

• Approximating MAPs for belief networks is NP-hard and other theorems
• scientific article; zbMATH DE number 2243356
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Treewidth and the Computational Complexity of MAP Approximations
• Finding MAPs for belief networks is NP-hard

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• An optimal approximation algorithm for Bayesian inference
• Approximating MAPs for belief networks is NP-hard and other theorems
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Finding MAPs for belief networks is NP-hard
• Fusion, propagation, and structuring in belief networks
• The computational complexity of probabilistic inference using Bayesian belief networks

Cited in

(12)

• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• An optimal approximation algorithm for Bayesian inference
• A model for compressing probabilities in belief networks
• Tree-width and the computational complexity of MAP approximations in Bayesian networks
• scientific article; zbMATH DE number 2243356 (Why is no real title available?)
• Approximating MAPs for belief networks is NP-hard and other theorems
• An algorithm for finding MAPs for belief networks through cost-based abduction
• Equivalences between maximum a posteriori inference in Bayesian networks and maximum expected utility computation in influence diagrams
• The complexity of finding \(k\)th most probable explanations in probabilistic networks
• Structure approximation of most probable explanations in Bayesian networks
• Universal Approximation Depth and Errors of Narrow Belief Networks with Discrete Units
• Complexity results for explanations in the structural-model approach

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

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