|

R197
Preliminary Empirical Evaluation of Anytime Weighted AND/OR Best-First Search for MAP
Natalia Flerova, Radu Marinescu, and Rina Dechter

Abstract
We explore the potential of anytime best-first search schemes for combinatorial optimization tasks over graphical models (e.g., MAP/MPE). We show that recent advances in extending best-first search into an anytime scheme have a potential for optimization for graphical models. Importantly, these schemes come with upper bound guarantees and are sometime competitive with known effective anytime branch-and-bound schemes.

[pdf]