Worst Case Analysis

One appealing definition of how good a solution a heuristic gets is to see how bad a heuristic can possibly be. If you know that the heuristic is never worst than, say, 1% above optimal, then you do not have to worry about which instances you have to solve next year. All will be solved within 1% of optimal.

The difficulty of this measure of solution quality is that heuristics are generally pretty bad in the worst case. If you are sufficiently hard working, it is not too difficult to come up with specially constructed examples where heuristics do poorly.

For instance, for the minimum spanning tree heuristic for the traveling salesman problem, it is possible to find examples where the heuristic is off by a factor of 2. This sounds pretty bad. In fact, all the heuristics we looked at can be worse than optimal by an arbitrary amount! In other words, there exists instances where nearest neighbor is off by a factor of 100, 1000, or even 1,000,000. Only the MST heuristic can be bounded at all. And knowing that it is always within a factor of 2 is not very appealing.