Optimizing searches via rare events.
Randomized search algorithms for hard combinatorial problems exhibit a large variability of performances. We study the different types of rare events which occur in such out-of-equilibrium stochastic processes and we show how they cooperate in determining the final distribution of running times. As a by-product of our analysis we show how search algorithms are optimized by random restarts.
Montanari
Andrea
A
Laboratoire de Physique Théorique de l'ENS, 24 rue Lhomond, 75231 Paris cedex 05, France. montanar@lpt.ens.fr
Zecchina
Riccardo
R