For a maximization problem $P$, I know that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|OPT|\ge |S| \ge \gamma\cdot|OPT|$ for $\gamma <1$ and $OPT$ the optimal solution for $P$.

Is there an alternative definition?

For example, can we say that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|S| \le \gamma\cdot|OPT|\le |OPT|$ for $\gamma<1$.


1 Answer 1


No, your definition isn't very useful. A $\gamma$-approximation algorithm is an algorithm that produces a solution which is not too bad compared to the optimal solution. In contrast, under your definition you are guaranteed to produce a solution which is somewhat worse than the optimal one.

Let's take as an example the maximum clique problem. Here is a $\gamma$-approximation algorithm for maximum clique under your definition: output an empty clique. This works for any $\gamma < 1$.

I suspect that what you intended to capture was that $\gamma$ is the "tight" approximation ratio of the algorithm. That is, you want $\gamma$ to be the supremal $\gamma$ such that the solution $S$ produced by the algorithm always satisfied $|S| \geq \gamma |OPT|$.

I just gave one definition of the tight approximation ratio, but here is another (equivalent) one. We say that $\gamma$ is the tight approximation ratio of the algorithm if the algorithm is a $\gamma$ approximation (under the usual definition), and for every $\epsilon > 0$ there is an instance on which the solution satisfies $|S| \leq (\gamma + \epsilon)|OPT|$. It's important here to include both parts of the definition.


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.