Pareto-Like Distributions in Random Binary CSP - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2003

Pareto-Like Distributions in Random Binary CSP


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 (213.88 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

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


  • HAL Id : lirmm-00269777 , version 1


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⟩
94 View
26 Download


Gmail Facebook X LinkedIn More