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 metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269777
Contributor : Christine Carvalho de Matos <>
Submitted on : Monday, April 9, 2018 - 7:52:23 PM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM

File

10.1.1.60.4869.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨lirmm-00269777⟩

Share

Metrics

Record views

131

Files downloads

32