Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
476148 | Computers & Operations Research | 2009 | 11 Pages |
Abstract
It is now a well-established fact that search algorithms can exhibit heavy-tailed behavior. However, the reasons behind this fact are not well understood. We provide a generative search tree model whose distribution of the number of nodes visited during search is formally heavy-tailed. Our model allows us to generate search trees with any degree of heavy-tailedness. We also show how the different regimes observed for the runtime distributions of backtrack search methods across different constrainedness regions of random CSP models can be captured by a mixture of the so-called stable distributions.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Alda Carvalho, Nuno Crato, Carla Gomes,