Approximating MAPs for belief networks is NP-hard and other theorems
type: Item
instance of: scholarly article
title: Approximating MAPs for belief networks is NP-hard and other theorems
zbMATH Open document ID: 0909.68077
DOI: 10.1016/S0004-3702(98)00043-5
published in: Artificial Intelligence
publication date: 1999-01-12T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1238314
zbMATH Keywords: Bayesian belief networks
zbMATH Keywords: dynamic abduction
zbMATH Keywords: next-best explanation
zbMATH Keywords: probabilistic reasoning
zbMATH Keywords: uncertainty
zbMATH Keywords: complexity
zbMATH Keywords: satisfiability
author: Ashraf M. Abdelbar
author: Sandra M. Hedetniemi
MaRDI profile type: Publication
cites work: The complexity of approximating MAPs for belief networks with bounded probabilities
cites work: Cost-based abduction and MAP explanation
cites work: The computational complexity of probabilistic inference using Bayesian belief networks
cites work: Approximating probabilistic inference in Bayesian belief networks is NP- hard
cites work: Q4198056
cites work: Q4692508
cites work: Optimization by Simulated Annealing
cites work: Q4734791
cites work: On the ratio of optimal integral and fractional covers
cites work: Q4298260
cites work: Fusion, propagation, and structuring in belief networks
cites work: Belief networks revisited
cites work: A linear constraint satisfaction approach to cost-based abduction
cites work: Finding MAPs for belief networks is NP-hard
Wikidata QID: Q128081837
Recommended article: The complexity of approximating MAPs for belief networks with bounded probabilities
Recommended article: Finding MAPs for belief networks is NP-hard
Recommended article: Approximating probabilistic inference in Bayesian belief networks is NP- hard
Recommended article: Q3979383
Recommended article: Approximate belief updating in max-2-connected Bayes networks is NP-hard
Recommended article: On the complexity of belief network synthesis and refinement
Recommended article: Tree-Width and the Computational Complexity of MAP Approximations in Bayesian Networks
Recommended article: A randomized approximation algorithm for probabilistic inference on bayesian belief networks
Recommended article: Approximate inference in Bayesian networks: parameterized complexity results
description: scientific article; zbMATH DE number 1238314