Restart strategies in optimization: parallel and serial cases ?
This paper addresses the problem of minimizing the average running time of the Las Vegas type algorithm, both in serial and parallel setups. The necessary conditions for the existence of an effective restart strategy are presented. We clarify the counter-intuitive empirical observations of super linear speedup and relate parallel speedup with the restart properties of serial algorithms. The general property of restart distributions is derived. The computational experiments involving the state-of-the-art optimization algorithm are provided.
restart super linear speedup parallel optimization las vegas algorithm