Optimal speedup of Las Vegas algorithms

Let A be a Las Vegas algorithm, i.e., A is a randomized algorithm that always produces the correct answer when its stops but whose running time is a random variable. The authors 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₁, then run A independent for a fixed amount of time t₂ , etc. The simulation stops if A completes its execution during any of the runs. Let S=(t₁, t ₂,. . .) be a strategy, and let l_A=inf_ST(A,S), where T(A,S) is the expected value of the running time of the simulation of A under strategy S. The authors describe a simple universal strategy S^univ , with the property that, for any algorithm A, T(A,S^univ)=O(l_A log(l_A)). Furthermore, they show that this is the best performance that can be achieved, up to a constant factor, by any universal strategy