Randomization in Backtrack Search: Exploiting Heavy-Tailed Profiles for Solving Hard Scheduling Problems

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.