STLS: Cutset-Driven Local Search For MPE
Alon Milchgrub and Rina Dechter

In this paper we present a cycle-cutset driven stochastic local search algorithm which approximates the optimum of sums of unary and binary potentials, called Stochastic Tree Local Search or ST LS. We study empirically two pure variants of ST LS against the state-of-the art GLS + scheme and against a hybrid.