1.10 Let A be an algorithm for minimization NP-optimization problem such that the expected cost of the solution produced by A is at most $\alpha OPT$, for a constant $\alpha>1$. What is the best approximation guarantee you can establish for this problem using algorithm A?

Hint: A guarantee of $2\alpha-1$ follows easily. to be honest, I don't really understand the question good. So usually when we want an approximation factor we take the ratio between solution of algorithm A and OPT of problem. could you explain the problem in other way! and how we get factor of $2\alpha-1$. Suppose I want to use Markov's bound, since the information we know is expected value. Thus, I would get $\alpha OPT/a$ for $a>0$. I don't see any logic here! I would like any help in terms of explanation!

Thank you!


1 Answer 1


I don't know what the author of the question means with "approximation guarantee" (is it defined earlier in the book?), so I am just going to tell you what you can derive from the information that's given.

If the expected value of the algorithm is $\mathbb{E}=v$, then the probability that the algorithm outputs a value larger than $kv$ is at most $\frac{1}{k}$, from Markov's bound, if the cost function never goes negative. So if you run the algorithm $t$ times, then the probability that the minimum value among all trials is greater than $kv$, is at most $k^{-t}$ (why? because the trials are independent).

There are no hard guarantees until there is more information.

  • $\begingroup$ Thank you for sharing information! "approximation guarantee" means "approximation factor" or "approximation ratio" so it has many names. So what I understand is that if we run the algorithm t*E[cost of algorithm A], then the probability that we get factor $\alpha OPT$ is so close to 0 $(1/k^t)$. I don't think this is a good bound, don't agree!! $\endgroup$
    – user777
    Oct 15, 2017 at 8:46
  • $\begingroup$ @user777 You're welcome! The bound I described is a little different than what you describe, so let me be clearer: if you run the algorithm $17$ times (for example), then the probability that the minimum value is greater than $2\alpha OPT$ is $2^{-17}\approx 1/64.000$. I don't think the approximation guarantee is the same as approximation factor; textbooks tend not to use these terms interchangeably. It probably has a definition, so I don't think we've understood the question well. For example, I haven't used the hint, and I see nothing related to $2\alpha-1$. $\endgroup$ Oct 15, 2017 at 9:47
  • $\begingroup$ the question is taken from Vazrani's textbook in approximation algorithm! $\endgroup$
    – user777
    Oct 15, 2017 at 13:42

Your Answer

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

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