4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – B.K. Nov 19 '17 at 21:51
  • 1
    $\begingroup$ @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$. $\endgroup$ – David Richerby Nov 19 '17 at 22:05
  • 1
    $\begingroup$ 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). $\endgroup$ – Sasho Nikolov Nov 20 '17 at 0:02
  • 1
    $\begingroup$ 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. $\endgroup$ – Neal Young Nov 20 '17 at 2:24
  • $\begingroup$ @SashoNikolov and Neal Young Thanks for hint. As I said I am beginner, so I haven't seen it yet. $\endgroup$ – B.K. Nov 20 '17 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.