I'm trying to show Amplification works for randomized algorithms, and for randomized approximation algorithms.


Amplification for randomized algorithms:
Given a randomized algorithm with time complexity $f(n)$ and error probability $\frac{1}{4}$, show there is an algorithm that solves the same problem, but with $O\left(f\left(n\right)log\left(\frac{1}{\varepsilon}\right)\right)$ run time, and error probability of $\varepsilon$, for a given $\varepsilon>0$.

I managed to show this running the original algorithm $k$ times, and choosing by majority vote the answer. Using Multiplicative Chernoff Bound (Which I've proven as well), I've shown $k\geq O\left(ln\left(\frac{1}{\varepsilon}\right)\right)$ gives us the required results.


Now I'm trying to do the same for approximation algorithms.

Amplification for randomized approximation algorithms:
Given a randomized approximation algorithm that returns an $\varepsilon$-additive-approximation with a probability of $\frac{3}{4}$, with run time complexity of $f\left(n\right)$, show there is an algorithm that returns an $\varepsilon$-additive-approximation with a probability of $1-\delta$, for the same problem, but with $O\left(f\left(n\right)log\left(\frac{1}{\delta}\right)\right)$ run time, for a given $\delta>0$.

The first thing that comes to my mind, is use a similar approach as before - run the original algorithm $k$ times, but this time instead of using majority vote, return the average.

I have to somewhow find a $k\geq O\left(ln\left(\frac{1}{\delta}\right)\right)$ such that $\mathbb{P}\left[\left|OPT-\frac{1}{k}\underset{i=1}{\overset{k}{\sum}}X_{i}\right|>\varepsilon\right]<\delta$.

I tried using the triangle inequality, then using union bound, but this doesn't lead me to being able to use Chernoff. In order to use Chernoff, I thought of defining an indicator random variable for each run of the original algorithm, stating if the result - $X_{i}$ is bad (that is, if $\left|X_{i}-OPT\right|>\varepsilon$), but this is where I get stuck.

Would appreciate any help. Thanks!

up vote 1 down vote accepted

Use the median instead of the mean. The median can only be bad if more than half the samples are bad.

The problem with the mean is that the mean could be bad from a lot of the samples being a little bit bad, or from a few of the samples being really bad. However, in general, you don't know the probabilities of different degrees of sample badness; just the probability of bad-versus-good.

  • That is indeed what I was missing. Managed to prove it using the Median. Thanks a lot! – Ungoliant Nov 29 at 22:34
  • I do wonder though why using the average didn't work out as average is usually used for these kind of things and has lots of nice qualities. Is it possible to show this using average? – Ungoliant Nov 30 at 0:21
  • 1
    I'm not sure it's possible with the mean, in general. Usually, all you know is that a single sample is bad with at most the given probability. Now, the mean of a set of samples could be bad because lots of the samples were a bit bad, or because one sample was really really bad, but, in general, you don't know the probabilities of different degrees of badness so you can't begin to bound the probability that the mean is bad. – David Richerby Nov 30 at 0:46
  • That makes perfect sense and helped sort out everything in my head :P Appreciate the help! – Ungoliant Nov 30 at 0:53
  • 1
    You're welcome! Glad it was useful for you. (I added the explanation of why the mean doesn't work to the answer.) – David Richerby Nov 30 at 0:57

Your Answer

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.