Publication - A New Look at the Easy-Hard-Easy Pattern of Combinatorial Search Difficulty

Authors: Mammen, Dorothy L., and Hogg, Tad
Title: A New Look at the Easy-Hard-Easy Pattern of Combinatorial Search Difficulty
Abstract: The easy-hard-easy pattern in the difficulty of combinatorial search problems as constraints are added has been explained as due to a competition between the decrease in number of solutions and increased pruning. We test the generality of this explanation by examining one of its predictions: if the number of solutions is held fixed by the choice of problems, then increased pruning should lead to a monotonic decrease in search cost. Instead, we find the easy-hard-easy pattern in median search cost even when the number of solutions is held constant, for some search methods. This generalizes previous observations of this pattern and shows that the existing theory does not explain the full range of the peak in search cost. In these cases the pattern appears to be due to changes in the size of the minimal unsolvable subproblems, rather than changing numbers of solutions.
Publication: Journal of Artificial Intelligence Research, Vol: 7, pp. 47 - 66
Date: July 1997
Sources: PS: http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume7/mammen97a.ps
HTML: http://www.cs.washington.edu/research/jair/abstracts/mammen97a.html
PDF: /Documents/mammen97a.pdf
Reference: Mammen, Dorothy L., and Hogg, Tad. A New Look at the Easy-Hard-Easy Pattern of Combinatorial Search Difficulty. Journal of Artificial Intelligence Research, Volume 7, pp. 47-66. July 1997.
bibtex: 
@article{Mammen-13,
  author    = "Dorothy L. Mammen and Tad Hogg",
  title     = "{A New Look at the Easy-Hard-Easy Pattern of
               Combinatorial Search Difficulty}",
  journal   = "Journal of Artificial Intelligence Research",
  volume    = "7",
  pages     = "47-66",
  month     = "July",
  year      = "1997",
  url       = "http://mas.cs.umass.edu/paper/13",
}