# How can an approximation ratio be less than 1?

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

## 1 Answer

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.

• Conclusio: check the definition in that book. – Raphael Jul 24 '15 at 6:13
• agree with Raphael. Definitions change. Sometimes $\epsilon$-approximation means finding an answer which is within $(1\pm \epsilon) Opt$. – Ran G. Jul 24 '15 at 13:16