Carla Gomes, Bart Selman, Ken McAloon, and Carol Tretkoff
We study the runtime profiles of complete backtrack-style search methods applied to hard scheduling problems. Such search methods often exhibit a large variability in performance due to the non-standard nature of their underlying cost distributions. The distributions generally exhibit very long tails or "heavy tails" and are best characterized by a general class of distributions that have no moments (i.e., an infinite mean, variance, etc.). We show how one can exploit the special nature of such distributions to significantly improve upon deterministic complete search procedures.