A Tapestry of Approximation Algorithms

Moralizing and propag-

ation in a tree of cliques

 

Lauritzen & Spiegelhalter, 1988

Polytrees

 

Kim & Pearl, 1983

Arc reversal and

reduction

 

Olmsted, 1983

Shachter, 1986, 1988.

Loop Cutset

conditioning

:

 Pearl, 1986

PIBNET is NP-hard 

Cooper, 1987

Clustering

 

Pearl  1988

Exact methods

Stochastic

simulation 

Logic sampling

Forward propagation

Henrion, 1986

Markov simulation

Gibbs sampling

 

Pearl, 1987

Approximate methods

Branch and bound

Search

methods

Importance

sampling

Likelihood

weighting

Fung & 

Chang  1989

Shachter & 

Peot 1989

NESTOR

 

Cooper, 1984

Set-covering: 

Peng & Reggia,

1987

FPRAS:

 

Chavez &

Cooper,

1989

 

Quickscore

 

Heckerman 1989

TopN

 

Henrion 1988, 1990

For QMR-DT network

S

 

Shwe & Cooper 1990

Bounded conditioning

Horvitz and Suermondt,

1988

Selective

conditioning

Dagum and Horvitz, 1992

Eric Horvitz, April 5, 2003