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!