Pareto-Like Distributions in Random Binary CSP

Abstract : Much progress has been made in terms of boosting the effectiveness of backtrack style search methods. In addition, during the last decade, a much better understanding of problem hardness, typical case complexity, and backtrack search behavior has been obtained. One example of a recent insight into backtrack search concerns so-called heavy-tailed behavior in randomized versions of backtrack search. Such heavy-tails explain the large variations in run-time often observed in practice. However, heavy-tailed behavior does certainly not occur on all instances. This has led to a need for a more precise characterization of when heavy-tailedness does and when it does not occur in backtrack search. In this paper, we provide such a characterization. In particular, we will identify different statistical regimes in the parameter space of a standard instance generation model. We show that whether backtrack search is heavy-tailed or not depends on the statistical regime of the instance space.
Type de document :
Communication dans un congrès
ACIA, 2003, Palma de Majorqua, Spain. 2003, Proceedings of ACIA 2003
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
Contributeur : Christine Carvalho de Matos <>
Soumis le : lundi 9 avril 2018 - 19:52:23
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Fichiers produits par l'(les) auteur(s)


  • HAL Id : lirmm-00269777, version 1



Christian Bessière, Cèsar Fernàndez, Carla Gomez, Magda Valls. Pareto-Like Distributions in Random Binary CSP. ACIA, 2003, Palma de Majorqua, Spain. 2003, Proceedings of ACIA 2003. 〈lirmm-00269777〉



Consultations de la notice


Téléchargements de fichiers