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!


1 Answer 1


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.

  • $\begingroup$ That is indeed what I was missing. Managed to prove it using the Median. Thanks a lot! $\endgroup$
    – Idra
    Nov 29, 2018 at 22:34
  • $\begingroup$ 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? $\endgroup$
    – Idra
    Nov 30, 2018 at 0:21
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 30, 2018 at 0:46
  • $\begingroup$ That makes perfect sense and helped sort out everything in my head :P Appreciate the help! $\endgroup$
    – Idra
    Nov 30, 2018 at 0:53
  • 1
    $\begingroup$ You're welcome! Glad it was useful for you. (I added the explanation of why the mean doesn't work to the answer.) $\endgroup$ Nov 30, 2018 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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