Restart Schedules for Ensembles of Problem Instances - Robotics Institute Carnegie Mellon University

Restart Schedules for Ensembles of Problem Instances

M. Streeter, D. Golovin, and S. F. Smith
Conference Paper, Proceedings of 22nd National Conference on Artificial Intelligence (AAAI '07), Vol. 2, pp. 1204 - 1210, July, 2007

Abstract

The mean running time of a Las Vegas algorithm can often be dramatically reduced by periodically restarting it with a fresh random seed. The optimal restart schedule depends on the Las Vegas algorithm's run length distribution, which in general is not known in advance and may differ across prob- lem instances. We consider the problem of selecting a single restart schedule to use in solving each instance in a set of instances. We present offline algorithms for computing an (approximately) optimal restart schedule given knowledge of each instance's run length distribution, generalization bounds for learning a restart schedule from training data, and online algorithms for selecting a restart schedule adaptively as new problem instances are encountered.

BibTeX

@conference{Streeter-2007-120468,
author = {M. Streeter and D. Golovin and S. F. Smith},
title = {Restart Schedules for Ensembles of Problem Instances},
booktitle = {Proceedings of 22nd National Conference on Artificial Intelligence (AAAI '07)},
year = {2007},
month = {July},
volume = {2},
pages = {1204 - 1210},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.