How to get the best factor for abstract algorithm that has expected cost?! 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&gt;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&gt;0$. I don't see any logic here! I would like any help in terms of explanation! 

Thank you!
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.