2
$\begingroup$

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

$\endgroup$
  • $\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 at 21:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.