Amplification for Randomized Algorithms

Question

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!

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.