**Problem Detail:**

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

###### Asked By : Erel Segal-Halevi

###### Answered By : Yuval Filmus

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.

Question Source : http://cs.stackexchange.com/questions/49220

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback