<p>Is there a known classification of randomized approximation algorithms, in the same vein as the distinction between Monte Carlo and Las Vegas algorithms for decision problems? (Or equivalently different randomized complexity classes for optimization problems, as <span class="math-container">$\mathsf{RP}$</span>, <span class="math-container">$\mathsf{BPP}$</span>, <span class="math-container">$\mathsf{ZPP}$</span>, etc. for decision problems.)</p>

<p>One could for instance classify randomized <span class="math-container">$\alpha$</span>-approximation algorithms in the following three classes (for say polytime algorithms):</p>

<ul>
<li>Las Vegas: Algorithm with expected polynomial time complexity, which always returns an <span class="math-container">$\alpha$</span>-approximation of the optimal result ;</li>
<li>Monte Carlo type I: Polynomial-time algorithm which returns a result that is an <span class="math-container">$\alpha$</span>-approximation of the optimal result with probability <span class="math-container">$p$</span> (for some <span class="math-container">$p&gt;1/2$</span> say) ;</li>
<li>Monte Carlo type II: Polynomial-time algorithm which returns a result whose expected approximation factor is <span class="math-container">$\alpha$</span>.</li>
</ul>

<h3>Questions:</h3>

<ol>
<li>Is my classification (sort of) exhaustive, or do I forget one (or more!) important possibility?</li>
<li>Is such a classification made in some reference, with links between the different cases, and some (better) names?</li>
</ol>

<p>The link between Monte Carlo type I and type II is for instance given in exercise 1.10 of <strong>Approximation algorithms</strong> by Vazirani (whose definition of a randomized approximation algorithm is btw "my" Monte Carlo type I).</p>

CC BY-SA 4.0
2018-11-09T09:27:58.933Z
I'm surprised by the negative vote. So if the voter could tell me why (for instance the question is stupid in some sense), I would be grateful!
Bruno
CC BY-SA 4.0
2018-11-13T19:55:03.417Z
(I'm not the downvoter.) 
Monte Carlo type I follows from Monte Carlo type II by the Markov Inequality. What seems to be missing is Monte Carlo type III: expected polynomial-time and expected $\alpha$-approximation?
Peter
CC BY-SA 4.0
2018-11-14T10:54:43.290Z
I don't think Markov inequality sufficient for this: What you may get for instance is that $\alpha$-approximation of type II implies $\alpha/2$-approximation of type I with probability $\ge1/2$. The better implication is from type II with approx. factor $\alpha$ to type I with approx. factor $(\alpha-\epsilon)$ for all $\epsilon >0$, using Chernoff bounds.
Bruno
<reference-request><approximation-algorithms><randomized-algorithms>
Classification of randomized approximation algorithms
Bruno
# Classification of randomized approximation algorithms

(Asked by: username_0 on 2018-11-08)

Is there a known classification of randomized approximation algorithms, in the same vein as the distinction between Monte Carlo and Las Vegas algorithms for decision problems? (Or equivalently different randomized complexity classes for optimization problems, as $\mathsf{RP}$, $\mathsf{BPP}$, $\mathsf{ZPP}$, etc. for decision problems.)

One could for instance classify randomized $\alpha$-approximation algorithms in the following three classes (for say polytime algorithms):

* Las Vegas: Algorithm with expected polynomial time complexity, which always returns an $\alpha$-approximation of the optimal result ;
* Monte Carlo type I: Polynomial-time algorithm which returns a result that is an $\alpha$-approximation of the optimal result with probability $p$ (for some $p>1/2$ say) ;
* Monte Carlo type II: Polynomial-time algorithm which returns a result whose expected approximation factor is $\alpha$.

### Questions:

1. Is my classification (sort of) exhaustive, or do I forget one (or more!) important possibility?
2. Is such a classification made in some reference, with links between the different cases, and some (better) names?

The link between Monte Carlo type I and type II is for instance given in exercise 1.10 of **Approximation algorithms** by Vazirani (whose definition of a randomized approximation algorithm is btw "my" Monte Carlo type I).

**Tags:** reference-request, approximation-algorithms, randomized-algorithms
> **Comments:**
> **username_0**: I'm surprised by the negative vote. So if the voter could tell me why (for instance the question is stupid in some sense), I would be grateful!  
> **username_1**: (I'm not the downvoter.)  Monte Carlo type I follows from Monte Carlo type II by the Markov Inequality. What seems to be missing is Monte Carlo type III: expected polynomial-time and expected $\alpha$-approximation?  
> **username_0**: I don't think Markov inequality sufficient for this: What you may get for instance is that $\alpha$-approximation of type II implies $\alpha/2$-approximation of type I with probability $\ge1/2$. The better implication is from type II with approx. factor $\alpha$ to type I with approx. factor $(\alpha-\epsilon)$ for all $\epsilon >0$, using Chernoff bounds.  

---

## 0 answers

