Optimal speedup of Las Vegas algorithms.

*(English)*Zbl 0797.68139Summary: 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.

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.

##### MSC:

68T15 | Theorem proving (deduction, resolution, etc.) (MSC2010) |

68Q25 | Analysis of algorithms and problem complexity |

##### Keywords:

expected running time; optimal strategy; proof search; theorem-proving; Las Vegas algorithm; randomized algorithm
PDF
BibTeX
XML
Cite

\textit{M. Luby} et al., Inf. Process. Lett. 47, No. 4, 173--180 (1993; Zbl 0797.68139)

Full Text:
DOI

##### References:

[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.