patternMinor
Does approximation ratio depend on the input size $n$?
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?
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.