# Does approximation ratio depend on the input size $n$?

I have started study of approximation algorithms and have confusion about the definition of approximation algorithm. I have two textbooks: by Cormen and the second one by Williamson.

Cormen's textbook says

If an algorithm achieves an approximation ratio of $\rho(n)$, we call it a $\rho(n)$-approximation algorithm.

Williamson's say

An $\alpha$-approximation algorithm for an optimization problem is a polynomial time algorithm that for all instances of the problem produces a solution whose value is within a factor of $\alpha$ of the value of an optimal solution.

So, the first definition defines approximation factor depended on $n$, while the second one does not mention of dependence of $\alpha$ on $n$.

Also I have never seen (yet at least) something like for example $(n/10)$-approximation algorithm, but seen $2$-approximation, or $3/2$-approximation.

My question: could someone clarify the precise definition of the approximation algorithm? (Wikipedia didn't help much). In particular, why do we need the dependence on $n$ if all ratios seem to be constant?

## 1 Answer

Not all NP-hard problems admit constant factor approximation algorithms (in polynomial-time). One such well-known example is the problem of finding a maximum clique, which cannot be approximated within a factor of $n^{1-\varepsilon}$ for any $\varepsilon > 0$ unless P = NP (see Wikipedia, though this is also mentioned in the introduction of Williamson & Shmoys).

• Yes, Williamson & Shmoys does mention it as a theorem (without a proof). But they still introduce and use the definition that does not mention anything about $n$, simply constant factor $\alpha$, not $\alpha(n)$. And later they mention $O(n^{1-\epsilon})$-approximation. This is why I confused. What is more, I have never seen an example saying, for example, $\ln(n)$-approximation or something like this. – HardFork Nov 19 '17 at 21:51
• @B.K. But it doesn't say "constant factor $\alpha$". It just says "factor $\alpha$". Cormen et al. are clearer, in that they explicitly state that the factor can be a function of $n$, but Williamson doesn't say that $\alpha$ can't depend on $n$. – David Richerby Nov 19 '17 at 22:05
• I am surprised you haven't seen a $O(\log n)$ factor approximation. Look up the set cover problem (which Williamson and Shmoys use a lot as an illustrative example). – Sasho Nikolov Nov 20 '17 at 0:02
• Yeah in general the approximation ratio can be defined as a function of any parameters of the input that you care to focus on. E.g. for set cover there are $O(\log \Delta)$-approximation algorithms, where $\Delta$ is the maximum set size. – Neal Young Nov 20 '17 at 2:24
• @SashoNikolov and Neal Young Thanks for hint. As I said I am beginner, so I haven't seen it yet. – HardFork Nov 20 '17 at 6:54