Publication Details
Title: Optimal Speedup of Las Vegas Algorithms
Author: M. Luby, A. Sinclair, and D. Zuckerman
Group: ICSI Technical Reports
Date: March 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-010.pdf
Overview:
Let A be a Las Vegas algorithm, i.e., A is a randomized algorithm that always produces the correct answer when it stops but whose running time is a random variable. We consider the problem of minimizing the expected time required to obtain an answer from~A using strategies which simulate A as follows: run A for a fixed amount of time t_1, then run A independently for a fixed amount of time t_2, etc. The simulation stops if A completes its execution during any of the runs. Let S = (t_1,t_2,...) be a strategy, and let ℓ_A=inf_{S}T(A,S), where T(A,S) is the expected value of the running time of the simulation of A under strategy S. We describe a simple universal strategy S^univ, with the property that, for any algorithm A, T(A,S^univ)=O(ℓ_A log(ℓ_A)). Furthermore, we show that this is the best performance that can be achieved, up to a constant factor, by any universal strategy.
Bibliographic Information:
ICSI Technical Report TR-93-010
Bibliographic Reference:
M. Luby, A. Sinclair, and D. Zuckerman. Optimal Speedup of Las Vegas Algorithms. ICSI Technical Report TR-93-010, March 1993
Author: M. Luby, A. Sinclair, and D. Zuckerman
Group: ICSI Technical Reports
Date: March 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-010.pdf
Overview:
Let A be a Las Vegas algorithm, i.e., A is a randomized algorithm that always produces the correct answer when it stops but whose running time is a random variable. We consider the problem of minimizing the expected time required to obtain an answer from~A using strategies which simulate A as follows: run A for a fixed amount of time t_1, then run A independently for a fixed amount of time t_2, etc. The simulation stops if A completes its execution during any of the runs. Let S = (t_1,t_2,...) be a strategy, and let ℓ_A=inf_{S}T(A,S), where T(A,S) is the expected value of the running time of the simulation of A under strategy S. We describe a simple universal strategy S^univ, with the property that, for any algorithm A, T(A,S^univ)=O(ℓ_A log(ℓ_A)). Furthermore, we show that this is the best performance that can be achieved, up to a constant factor, by any universal strategy.
Bibliographic Information:
ICSI Technical Report TR-93-010
Bibliographic Reference:
M. Luby, A. Sinclair, and D. Zuckerman. Optimal Speedup of Las Vegas Algorithms. ICSI Technical Report TR-93-010, March 1993