On the Empirical Evaluation of Las Vegas Algorithms

We advocate a new methodology for empirically analysing the behaviour of Las Vegas Algorithms, a large class of probabilistic algorithms comprising prominent methods such as local search algorithms for SAT and CSPs, like WalkSAT and the Min-Conflicts Heuristic, as well as more general metaheuristics like Genetic Algorithms, Simulated Annealing, Iterated Local Search, and Ant Colony Optimization. Our method is based on measuring and analysing run-time distributions (RTDs) for individual problem instances. We discuss this empirical methodology and its application to Las Vegas Algorithms for various problem domains. Our experience so far strongly suggests that using this approach for studying the behaviour of Las Vegas Algorithms can provide a basis for improving the understanding of these algorithms and thus facilitate further successes in their development and application