snippetMinor
Providing Tight Example in Approximation Algorithm Analysis
Viewed 0 times
tightapproximationexampleanalysisprovidingalgorithm
Problem
Let's say I found a 2-approximation algorithm for a certain problem and I want to show that the analysis is tight.
Do I now need to come up with an example of generic size $n$ or does it suffice to show that I have an example of size $10$ for which the algorithm yields $2OPT$?
Do I now need to come up with an example of generic size $n$ or does it suffice to show that I have an example of size $10$ for which the algorithm yields $2OPT$?
Solution
That depends on your definition of approximation ratio. Normally the approximation ratio is defined as the worst ratio between optimal solution and the one produced by your algorithm. If this is the case, all you need to show that the ratio is tight is come up with one bad example.
Sometimes, however, you prove something like $ALG \leq 2OPT + 1$. This means that your approximation ratio is really $2 + o(1)$. To show that this is tight, you will need an example for infinitely many sizes (but not necessarily for a generic size; perhaps all your examples have even size).
Sometimes, however, you prove something like $ALG \leq 2OPT + 1$. This means that your approximation ratio is really $2 + o(1)$. To show that this is tight, you will need an example for infinitely many sizes (but not necessarily for a generic size; perhaps all your examples have even size).
Context
StackExchange Computer Science Q#6140, answer score: 6
Revisions (0)
No revisions yet.