Pareto-Like Distributions in Random Binary CSP - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2003

Pareto-Like Distributions in Random Binary CSP

Résumé

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.
Fichier principal
Vignette du fichier
10.1.1.60.4869.pdf (213.88 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00269777 , version 1 (09-04-2018)

Identifiants

  • HAL Id : lirmm-00269777 , version 1

Citer

Christian Bessiere, Cèsar Fernàndez, Carla P. Gomez, Magda Valls. Pareto-Like Distributions in Random Binary CSP. ACIA, 2003, Palma de Majorqua, Spain. ⟨lirmm-00269777⟩
96 Consultations
35 Téléchargements

Partager

Gmail Mastodon Facebook X LinkedIn More