Résumé: Stochastic local search (SLS) algorithms have been successfully applied to hard combinatorial problems from different domains. Due to their inherent randomness, the run-time behaviour of these algorithms is characterized by a random variable. The detailed knowledge of the run-time distribution provides important information about the behaviour of SLS algorithms. In this paper we investigate the empirical run-time distributions for WalkSAT, one of the most powerful SLS algorithms for the Propositional Satisfiability Problem (SAT). Using statistical analysis techniques, we show that on hard Random-3-SAT problems, WalkSAT's run-time behaviour can be characterized by exponential distributions. This characterization can be generalized to various SLS algorithms for SAT and to encoded problems from other domains. This result also has a number of consequences which are of theoretical as well as practical interest. One of these is the fact that these algorithms can be easily parallelized such that optimal speedup is achieved for hard problem instances.

Langue: Anglais