Randomized Algorithms: High-Probability vs. Expectation

Question

Hopefully this question isn't too general, but I was wondering what the relationship is between randomized algorithms that perform well with high-probability and those that perform well in expectation. My question is motivated by the definition of a randomized $\alpha$-approximation algorithm given here, namely that it is a polynomial-time algorithm that produces a solution within $\alpha$ of OPT in expectation or with high probability. I also found that the first few pages of this source provides some good insight into the high-probability vs. expectation approaches, but I still have questions.

• Can you always transform an algorithm that achieves an $\alpha$-approximation in expectation to one that achieves this with high probability, and vice versa? (Ostensibly by rerunning the algorithm multiple [a polynomial number] of times.)
• If not, is one harder than the other to obtain? (I would think that if you fix $\alpha$, a high-probability algorithm would always be harder to find/less likely to exist. Or maybe you can always find one, but the approximation ratio will become worse.)

Thanks for the help!

Answer 1

If you have an algorithm that is an $\alpha$-approximation in expectation, then you can construct an algorithm that is a $(1+\epsilon)\alpha$-approximation with high probability, for any $\epsilon>0$. In particular, by Markov's inequality, if you run the algorithm, then with probability at least $1-1/(1+\epsilon)$ it will output a $(1+\epsilon)\alpha$-approximation. So, if you run the algorithm about $(c \log n)/\epsilon$ times and keep the best output among all of those trials, with probability about $1-1/n^c$ you will find a $(1+\epsilon)\alpha$-approximation.

If you have an algorithm that is an $\alpha$-approximation with high probability, there are no guarantees about the expectation. It's possible that with very small probability (probability $1/n^c$), it outputs an extremely bad solution (one with exponentially large approximation factor), and in all other cases it outputs an $\alpha$-approximation. In this case, the expected value of the approximation factor will be very large, even though it has a very small probability to output such a bad solution.