# Best polynomial-time approximation factor for NP-optimization problems

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

Questions:

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

• 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. – Yonatan N Jan 5 at 21:27