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 [14 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269777
Contributeur : Christine Carvalho de Matos <>
Soumis le : lundi 9 avril 2018 - 19:52:23
Dernière modification le : mercredi 11 avril 2018 - 11:50:29

Fichier

10.1.1.60.4869.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00269777, version 1

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

56

Téléchargements de fichiers

5