Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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$?

Asked By : Ziggy

Answered By : emab

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.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback