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)&lt; 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.