Optimal Speedup of Las Vegas Algorithms

TitleOptimal Speedup of Las Vegas Algorithms
Publication TypeTechnical Report
Year of Publication1993
AuthorsLuby, M., Sinclair A., & Zuckerman D.
Other Numbers798

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 Notes

ICSI Technical Report TR-93-010

Abbreviated Authors

M. Luby, A. Sinclair, and D. Zuckerman

ICSI Publication Type

Technical Report