8
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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).

$\endgroup$
3
$\begingroup$

If your algorithm achieves a 1.5 approximation on all but a finite set $S$ of instances, on which your algorithm achieves a 2-approximation, then you could "improve" your algorithm by "hardwiring" the optimal solutions for the instances in $S$ into your algorithm. In short, for theoretical purposes, an algorithm that succeeds on all but a finite set of instances is just as good as an algorithm that always succeeds. Therefore, a theoretically meaningful tight example is actually an infinite family of tight examples. As Yuval says, any infinite family of examples will do, you don't need an example for every instance size.

That being said, most problems allow you to "scale up" a small example into a larger one.

$\endgroup$
  • $\begingroup$ But if there are too many bad instances on which you want the algorithm to hardwire, don't you run into the problem that your algorithm doesn't run in polytime anymore, since you have to check which hardwire-case to apply? $\endgroup$ – user695652 Oct 18 '12 at 18:47
  • $\begingroup$ @user695652 "finite" $S$ means that $|S| = O(1)$. you can choose which case to apply in $O(1)$ time. of course that might be a HUGE constant -- but that's the nature of asymptotic analysis. $\endgroup$ – Sasho Nikolov Oct 18 '12 at 22:11

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.