3
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

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

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.