AAAI Publications, Seventh Annual Symposium on Combinatorial Search

Font Size: 
STLS: Cycle-Cutset-Driven Local Search For MPE
Alon Milchgrub, Rina Dechter

Last modified: 2014-07-02


In this paper we present Stochastic Tree-based Local Search or STLS, a local search algorithm combining the notion of cycle-cutsets with the well-known Belief Propagation to approximatethe optimum of sums of unary and binary potentials. This is done by the previously unexplored concept oftraversal from one cutset to another and updating the induced forest, thus creating a local search algorithm, whose updatephase spans over all the forest variables. We study empirically two pure variants of STLS against the state-of-the art GLS+ scheme and against a hybrid.


MPE; Cycle-Cutset; Baysian-Inference; Stochastic-Local-Search

Full Text: PDF