Let us say that a function $f(n)$ is the best approximation factor for an NP-optimization problem, if both of the following hold:

  1. There exist a polynomial-time algorithm $A,$ and an integer $n_0$, such that $A$ provides an $f(n)$-approximation for the NP-optimization problem for every instance with size $n\geq n_0$. (Note: the role of $n_0$ is merely to treat potentially deviant small instances, which might make the function "ugly.")

  2. There is no polynomial-time $(1-o(1))f(n)$ approximation, unless $P=NP$.

A classic example where such a best approximation is known is the SET COVER problem (for a summary and references see its Wikipedia page): the Greedy Algorithm provides an $\ln n$ approximation, but there is no $(1-o(1))\ln n$ approximation, unless $P=NP$.


  1. Which are some other interesting NP-optimization problems for which a best approximation factor, along with its realizing algorithm, are known?

  2. Are there any counterexamples, i.e., NP-optimization problems, for which such a best approximation cannot exist, unless $P=NP$?

  • $\begingroup$ The statement isn't completely formally defined, but it's likely that any NP-hard problem with a PTAS will satisfy most formal restatements the second criterion. $\endgroup$ – Yonatan N Jan 5 '19 at 21:27

Your Answer

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

Browse other questions tagged or ask your own question.