Average Case Analysis

Knowing the worst case example is by no means the end of the story, however. Most worst case examples are highly contrived and show none of the features that we expect from real-world problems. If worst case examples do not occur in practice, it seems silly to base our decisions on them. Therefore, an alternative approach is to talk about ``typical'' examples.

One approach to quantify this idea is to create a probabilistic model that reflects some real-world behavior. For instance, for the TSP, points might be scattered uniformly in a square (in 2 dimensions) or cube (in three dimensions) and costs are taken to be the distances between the points.

Once we have a model, we want to determine how our heuristics work ``on average'' assuming the data comes from this model. This can be done in one of two ways: either the average tour length can be computed directly using such analytical tools as stochastic analysis, or many, many instances can be solved and statistical analysis be used to get the average tour length.

Our break-combine heuristic has the interesting property that as the number of points goes to infinity, the average tour length in the uniform 2-dimensional model goes to the optimal value. The other heuristics do not have this property.

While this method seems to get closer to the idea of a typical problem, there are still a few weaknesses. No real world problem I know of actually comes from a random draw. The random model may be more or less right, but any deviation from the model may radically change the conclusions. Also, average case behaviour says little about variance, which adds a level of complexity. Finally, analytical solutions are very, very difficult to get, while the usefulness of statistical analysis of many runs is so expensive that it might not be worth the effort.