For a certain maximization problem, a "constant-factor approximation algorithm" is an algorithm that returns a solution with value at least $F\cdot \textrm{Max}$, where $F<1$ is some constant and $\textrm{Max}$ is the exact maximal value.

What term describes an algorithm in which the approximation factor is a function $F(n)$ of the problem size, and $F(n)\to 1$ as $n\to \infty$?

  • 1
    $\begingroup$ Is approximation factor even the right notion in such circumstances. For example, a constant additive error has the property that, as $\mathrm{OPT}\to\infty$, $(\mathrm{OPT}+\mathrm{err})/\mathrm{OPT}\to 1$. $\endgroup$ – David Richerby Nov 8 '15 at 15:00

You can say your algorithm is asymptotically optimal. One example is universal codes, which are a certain type of codes for the natural numbers. They satisfy the following property. Let $D$ be a monotone probability distribution over the natural numbers, that is $\Pr[D=n] > \Pr[D=n+1]$. The average codeword length under a universal code is $H(D)(1 + o(1))$. Since $H(D)$ is the optimal length, universal codes are asymptotically optimal, in exactly the same sense as the one you're after.

| cite | improve this answer | |

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.