HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How can an approximation ratio be less than 1?

Submitted by: @import:stackexchange-cs··
0
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$?

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.

Context

StackExchange Computer Science Q#44690, answer score: 4

Revisions (0)

No revisions yet.