HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theapproximationsizeinputdoesratiodepend

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#84161, answer score: 4

Revisions (0)

No revisions yet.