2
$\begingroup$

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!

| cite | improve this question | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for this fantastic answer! I'm probably missing something obvious, but I am stuck at checking the $(c \log n) / \epsilon$. The probability of failure in one trial is at most $\frac{1}{1 + \epsilon}$, so we want to show that $$\left( \frac{1}{1 + \epsilon} \right)^{(c \log n) / \epsilon}$$ is small, i.e., about $1/n^c$. Clearly we are allowed to upper bound the expression. At first I was thinking you could apply $1 + \epsilon \le e^\epsilon$ in the denominator, but this would make the entire expression smaller, so it is a no go. What am I missing? $\endgroup$ – kanso37 Jul 13 at 5:03
  • $\begingroup$ Also, does this result generalize to maximization problems as well? The problem being that Markov's inequality is now upper bounding the probability of the good event instead of the bad event. I tried to find some sort of "reverse Markov's inequality," but it seems that such inequalities are really ugly and not obviously applicable. $\endgroup$ – kanso37 Jul 13 at 5:14
  • 1
    $\begingroup$ @kanso37, When $\epsilon$ is small, $1/(1+\epsilon)\approx 1-\epsilon$, and $(1-\epsilon)^{1/\epsilon} \approx 1/e$. You should be able to take it from there. I haven't thought about maximization algorithms. The answer might be different, if solutions have non-negative value. $\endgroup$ – D.W.♦ Jul 13 at 6:02
  • $\begingroup$ Thank you so much! $\endgroup$ – kanso37 Jul 14 at 1:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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