  Stochastic search algorithms are among the most sucessful approaches for
solving hard combinatorial problems. A large class of stochastic search
approaches can be cast into the framework of Las Vegas Algorithms (LVAs). As
the run-time behavior of LVAs is characterized by random variables, the
detailed knowledge of run-time distributions provides important information for
the analysis of these algorithms. In this paper we propose a novel methodology
for evaluating the performance of LVAs, based on the identification of
empirical run-time distributions. We exemplify our approach by applying it to
Stochastic Local Search (SLS) algorithms for the satisfiability problem (SAT)
in propositional logic. We point out pitfalls arising from the use of improper
empirical methods and discuss the benefits of the proposed methodology for
evaluating and comparing LVAs.

Artificial Intelligence