Restart strategies in optimization: parallel and serial cases

详细信息    查看全文

• 作者：Oleg V. Shylo ; Timothy Middelkoop ; Panos M. Pardalos
• 关键词：Parallel optimization ; Restart ; Super linear speedup ; Las Vegas algorithm
• 刊名：Parallel Computing
• 出版年：2011
• 出版时间：January 2011
• 年：2011
• 卷：37
• 期：1
• 页码：60-68
• 全文大小：438 K

文摘

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.