Cheap and Secure Web Hosting Provider : See Now

# [Answers] How can an approximation ratio be less than 1?

, ,
Problem Detail:

A question in my algorithms text-book requires that we,

Describe an efficient $(1 - \frac{1}{k})$ -approximation algorithm for this problem.

It is my understanding that $(1 - \frac{1}{k})$ being $p(n)$ is the approximation ratio and that an approximate solution differs from an optimal solution by a factor of $p(n)$. In that case, if $p(n)< 1$ wouldn't the approximation be better than optimal?

How can the approximation ratio be less than $1$?

For maximization problems, if the optimal solution is $O^*$ and the worst possible approximate solution is $O$, then the standard way is to consider $O^*/O$ as the approximation ratio. But in some text books, the ratio $O/O^*$ is considered for both minimization and maximization problems and it causes the ratio to be smaller than 1.

You may refer to Approximation Algorithm for more details.