Optimizing searches via rare events |
| |
Authors: | Montanari Andrea Zecchina Riccardo |
| |
Affiliation: | Laboratoire de Physique Théorique de l'ENS, 24 rue Lhomond, 75231 Paris cedex 05, France. montanar@lpt.ens.fr |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 PubMed 等数据库收录! |
|