5
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
5
  • $\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$
    – HardFork
    Commented Nov 19, 2017 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
    Commented Nov 19, 2017 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
    Commented Nov 20, 2017 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
    Commented Nov 20, 2017 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$
    – HardFork
    Commented Nov 20, 2017 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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