We recently in computational complexity class dealt with approximation algorithms and I was wondering how one would prove a heuristic having a certain ratio in regards to the optimal version. Looking at some notes it seems that one has to relate the approximation to an intermediate algorithm, right?


It's not necessary to compare to an intermediate algorithm, just to the best possible.

For example, consider the following terrible algorithm for approximating the distance between two vertices in a graph: if the vertices are adjacent, return $1$; otherwise, return $n$, the number of vertices. This gives an $n/2$ approximation: in the worse case, the true distance is $2$ but the algorithm returns $n$.

But perhaps you're concerned that we might not know the true optimal value – after all, it's probably hard to analyze and compute. That's why we're using an approximation algorithm, right? So let's imagine that the distance between vertices is really difficult to calculate so we don't actually know what the worst case of our approximation algorithm is. At that point, you can start using approximations or, rather, bounds on the optimal value. So, for example, somebody might say, "Hey, I've no idea what the greatest possible distance between two vertices in a graph is but I know it's the length of the shortest path. A path has to use some set of edges, and use them once each. I know there can't be more than $n^2$ different edges in a graph, so the worst-case distance can't be more than $n^2\!$. Therefore, the approximation ratio can't be any worse than $n^2/2$." And they'd be right: the approximation ratio isn't any worse than that. The "more sophisticated" analysis in the previous paragraph gave a better bound on the approximation ratio.

| cite | improve this answer | |
  • $\begingroup$ You write in 2nd paragraph: "in the worse case, the true distance is n−1 but the algorithm returns 2". I may misunderstand, but should it not be: "in the worst case, the true distance is 2 but the algorithm returns n"? However, I would rather return always (n-1)/2 ... but I am completely ignorant of the topic. $\endgroup$ – babou Oct 30 '14 at 14:03
  • $\begingroup$ @Babou Sorry, yes, I got that the wrong way round. And, yes, returning $(n-1)/2$ would make the approximation ratio better by a factor of two. My point was just to give an easily analyzed example, not to produce a realistic algorithm. (And, since I goofed the analysis anyway, you can only imagine what a mess I'd have made of an algorithm that was harder to analyze!) $\endgroup$ – David Richerby Oct 30 '14 at 14:18
  • $\begingroup$ It is ok. I was really ignorant of the issue, so I read carefully, and got the idea... and noticed the bug. What bothers me though is that I was apparently the only one ... :) $\endgroup$ – babou Oct 30 '14 at 19:26

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.