zbMATH — the first resource for mathematics

Optimal speedup of Las Vegas algorithms. (English) Zbl 0797.68139
Summary: 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 \({\mathcal S}= (t_ 1,t_ 2,\dots)\) be a strategy, and let \(\ell_ A= \inf_{\mathcal S} T(A,{\mathcal S})\), where \(T(A,{\mathcal S})\) is the expected value of the running time of the simulation of \(A\) under strategy \({\mathcal S}\).
We describe a simple universal strategy \({\mathcal S}^{\text{univ}}\), with the property that, for any algorithm \(A\), \(T(A,{\mathcal S}^{\text{univ}})= O(\ell_ A\log (\ell_ A))\). Furthermore, we show that this is the best performance that can be achieved, up to a constant factor, by any universal strategy.

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Alt, H.; Guibas, L.; Mehlhorn, K.; Karp, R.; Wigderson, A., A method for obtaining randomized algorithms with small tail probabilities, Tech. rept. TR-91-057, (1991), International Computer Science Institute Berkeley · Zbl 0857.68057
[2] Ertel, W., OR-parallel theorem proving with random competition, (), 226-237, Lecture Notes in Artificial Intelligence
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.