How to correctly define the ratio of an approximation algorithm?

Question

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$.

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.