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!

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).
• 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!! – user777 Oct 15 '17 at 8:46
• @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$. – Lieuwe Vinkhuijzen Oct 15 '17 at 9:47