Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Christine Carvalho de Matos Connect in order to contact the contributor
Submitted on : Monday, April 9, 2018 - 7:52:23 PM
Last modification on : Monday, October 11, 2021 - 1:24:08 PM

Files produced by the author(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. ⟨lirmm-00269777⟩



Record views


Files downloads