Restart Schedules for Ensembles of Problem Instances
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.
Cite
Text
Streeter et al. "Restart Schedules for Ensembles of Problem Instances." AAAI Conference on Artificial Intelligence, 2007.Markdown
[Streeter et al. "Restart Schedules for Ensembles of Problem Instances." AAAI Conference on Artificial Intelligence, 2007.](https://mlanthology.org/aaai/2007/streeter2007aaai-restart/)BibTeX
@inproceedings{streeter2007aaai-restart,
title = {{Restart Schedules for Ensembles of Problem Instances}},
author = {Streeter, Matthew J. and Golovin, Daniel and Smith, Stephen F.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2007},
pages = {1204-1210},
url = {https://mlanthology.org/aaai/2007/streeter2007aaai-restart/}
}