The complexity of approximating MAPs for belief networks with bounded probabilities
type: Item
instance of: scholarly article
title: The complexity of approximating MAPs for belief networks with bounded probabilities
zbMATH Open document ID: 0952.68137
DOI: 10.1016/S0004-3702(00)00076-X
published in: Artificial Intelligence
publication date: 2000-12-12T00:00:00Z
review text: Probabilistic inference and Maximum A Posteriori (MAP) explanation are two important and related problems on Bayesian belief networks. Both problems are known to be NP-hard for both approximation and exact solution. In 1997, Dagum and Luby showed that efficiently approximating probabilistic inference is possible for belief networks in which all probabilities are bounded away from \(0.\) In this paper, we show that the corresponding result for MAP explanation does not hold: finding, or approximating, MAPs for belief networks remains NP-hard for belief networks with probabilities bounded within the range \([l,u]\) for any \(0<l<0.5<u<1.\) Our results cover both deterministic and randomized approximation.
Mathematics Subject Classification ID: 68T35
zbMATH DE Number: 1542380
zbMATH Keywords: Bayesian belief networks
zbMATH Keywords: complexity
zbMATH Keywords: local variance bound
zbMATH Keywords: satisfiability
zbMATH Keywords: bipartite networks
author: Ashraf M. Abdelbar
author: Stephen T. Hedetniemi
author: Sandra M. Hedetniemi
MaRDI profile type: Publication
cites work: Approximating MAPs for belief networks is NP-hard and other theorems
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: An optimal approximation algorithm for Bayesian inference
cites work: Q4198056
cites work: Q4298260
cites work: Fusion, propagation, and structuring in belief networks
cites work: Finding MAPs for belief networks is NP-hard
description: scientific article; zbMATH DE number 1542380