The complexity of approximating MAPs for belief networks with bounded probabilities

DOI10.1016/S0004-3702(00)00076-XzbMATH Open0952.68137MaRDI QIDQ1589640FDOQ1589640

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

Publication date: 12 December 2000

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Finding MAPs for belief networks is NP-hard
• The computational complexity of probabilistic inference using Bayesian belief networks
• Fusion, propagation, and structuring in belief networks
• Approximating MAPs for belief networks is NP-hard and other theorems
• An optimal approximation algorithm for Bayesian inference

Cited In (12)

• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• A model for compressing probabilities in belief networks
• An optimal approximation algorithm for Bayesian inference
• Tree-width and the computational complexity of MAP approximations in Bayesian networks
• Title not available (Why is that?)
• An algorithm for finding MAPs for belief networks through cost-based abduction
• Approximating MAPs for belief networks is NP-hard and other theorems
• 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)