Statistical Regimes Across Constrainedness Regions
MetadataShow full item record
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 variance in runtime 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. We identify different statistical regimes of the tail of the runtime distributions of randomized backtrack search methods and show how they are correlated with the Bsophistication^ of the search procedure combined with the inherent hardness of the instances. We also show that the runtime distribution regime is highly correlated with the distribution of the depth of inconsistent subtrees discovered during the search. In particular, we show that an exponential distribution of the depth of inconsistent subtrees combined with a search space that grows exponentially with the depth of the inconsistent subtrees implies heavy-tailed behavior.
Is part ofConstraints, 2005, vol. 10, p. 317-337
European research projects
Showing items related by title, author, creator and subject.
Béjar Torres, Ramón; Domshlak, Carmel; Fernàndez Camon, César; Gomes, Carla; Krishnamachari, Bhaskar; Selman, Bart; Valls Marsal, Magda (Elsevier, 2005)We introduce SensorDCSP, a naturally distributed benchmark based on a real-world application that arises in the context of networked distributed systems. In order to study the performance of Distributed CSP (DisCSP) ...
Ansótegui Gil, Carlos José; Béjar Torres, Ramón; Fernàndez Camon, César; Gomes, Carla; Mateu Piñol, Carles (Springer, 2011)Sudoku problems are some of the most known and enjoyed pastimes, with a never diminishing popularity, but, for the last few years those problems have gone from an entertainment to an interesting research area, a twofold ...
Argelich Romà, Josep; Béjar Torres, Ramón; Cabiscol i Teixidó, Alba; Fernàndez Camon, César; Manyà Serres, Felip; Gomes, Carla (European Conference on Planning, 2013)We present a random generator of partially complete round robin timetables that produces exclusively satisfiable instances, and provide experimental evidence that there is an easy-hard-easy pattern in the computational ...