Randomization in backtrack search: exploiting heavy-tailed profiles for solving hard scheduling problems

Abstract

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 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.