<p>Rapid restarts in SAT solving are one area where the sequence introduced in Luby,Sinclair,Zuckerman is used. See for example Section 2.1 in <a href="http://www.st.ewi.tudelft.nl/~marijn/publications/rapid.pdf" rel="nofollow">http://www.st.ewi.tudelft.nl/~marijn/publications/rapid.pdf</a> for some references.</p>

CC BY-SA 3.0
2012-11-21T00:13:24.647Z
Restart strategies are used in CSP solvers too. CSP is more general than SAT. Despite the Luby sequence being nice theoretically, other sequences are also used in practice.
Juho
CC BY-SA 3.0
2012-11-20T15:39:01.427Z
2012-11-20T15:39:01.427Z
Klaus Draeger
<p>In [Randomized Algorithms, Motwani and Raghavan] book, it is stated that the method of independent iterations to reduce the error probability in Monte Carlo algorithms (amplification according to Wikipedia) has its analogy in Las vegas algorithms. The authors then cited the following references:</p>

<ol>
<li>Alt, Helmut, et al. "A method for obtaining randomized algorithms with small tail probabilities." Algorithmica 16.4 (1996): 543-547.</li>
<li>Luby, Michael, Alistair Sinclair, and David Zuckerman. "Optimal speedup of Las Vegas algorithms." Information Processing Letters 47.4 (1993): 173-180.</li>
</ol>

<p>These suggestions of the mentioned papers are a bet very generalized in my opinion. I am wondering - are there well-known algorithms that use the concepts introduced in the previous papers ? </p>

<ds.algorithms><reference-request><randomized-algorithms>
Independent iterations in Las Vegas algorithms
AJed
# Independent iterations in Las Vegas algorithms

(Asked by: username_0 on 2012-11-20)

In [Randomized Algorithms, Motwani and Raghavan] book, it is stated that the method of independent iterations to reduce the error probability in Monte Carlo algorithms (amplification according to Wikipedia) has its analogy in Las vegas algorithms. The authors then cited the following references:

1. Alt, Helmut, et al. "A method for obtaining randomized algorithms with small tail probabilities." Algorithmica 16.4 (1996): 543-547.
2. Luby, Michael, Alistair Sinclair, and David Zuckerman. "Optimal speedup of Las Vegas algorithms." Information Processing Letters 47.4 (1993): 173-180.

These suggestions of the mentioned papers are a bet very generalized in my opinion. I am wondering - are there well-known algorithms that use the concepts introduced in the previous papers ?

**Tags:** ds.algorithms, reference-request, randomized-algorithms

---

## 1 answers

### Answer by username_1 on 2012-11-20. Score: 4 | Accepted answer

Rapid restarts in SAT solving are one area where the sequence introduced in Luby,Sinclair,Zuckerman is used. See for example Section 2.1 in <http://www.st.ewi.tudelft.nl/~marijn/publications/rapid.pdf> for some references.

> **Comments:**
> **username_2**: Restart strategies are used in CSP solvers too. CSP is more general than SAT. Despite the Luby sequence being nice theoretically, other sequences are also used in practice.  

---

