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

  • 1
    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 Nov 9 at 9:27
  • (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 Nov 13 at 19:55
  • 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 2 days ago

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.