Algorithms in a Nutshell

Approximation Algorithms

An approximation algorithm seeks answers that are close to, but not necessarily as good as, the true answer. The general tradeoff is to decrease the time by which the answer is returned at the expense of accuracy.

As an example of the speed improvement of solving problems when exact answers aren't necessary but good answers are acceptable, we consider the Traveling Salesman Problem (TSP). In TSP, we are given a set of cities to visit and the set of distances between each pair of cities. We must determine the least-cost tour that starts at a city, visits each city exactly once, and returns to the originating city of the tour. This problem is one of the most heavily researched of all problems in computer science, and it is highly unlikely that there exists a polynomial time algorithm that solves TSP; that is, no algorithm can solve TSP in O(n^k) for fixed integer k. It belongs to a large class of problems (the NP-hard problems) for which it is strongly believed that finding an exact answer is inherently very difficult.

But assuming it is known that the distances between locations satisfy the triangular inequality (i.e., for all triples of locations a, b, c, the distance from a to b is never longer than the distance from a to c plus the distance from c to b), Christofides (1976) designed an efficient algorithm to solve the problem that constructs a tour that is never more than 50% longer than a shortest tour.