snippetMinor
How can an approximation ratio be less than 1?
Viewed 0 times
canapproximationthanlesshowratio
Problem
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$?
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$?
Solution
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.
You may refer to Approximation Algorithm for more details.
Context
StackExchange Computer Science Q#44690, answer score: 4
Revisions (0)
No revisions yet.