# Proving approximation ratio

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?

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.
• @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!) – David Richerby Oct 30 '14 at 14:18