Chapter notes

Although methods that do not necessarily compute exact solutions have been known for thousands of years (for example, methods to approximate the value of π), the notion of an approximation algorithm is much more recent. Hochbaum credits Garey, Graham, and Ullman [109] and Johnson [166] with formalizing the concept of a polynomial-time approximation algorithm. The first such algorithm is often credited to Graham [129] and is the subject of Problem 35-5.

Since this early work, thousands of approximation algorithms have been designed for a wide range of problems, and there is a wealth of literature on this field. Recent texts by Ausiello et al. [25], Hochbaum [149], and Vazirani [305] deal exclusively with approximation algorithms, as do surveys by Shmoys [277] and Klein and Young [181]. Several other texts, such as Garey and Johnson [110] and Papadimitriou and Steiglitz [237], have significant coverage of approximation algorithms as well. Lawler, Lenstra, Rinnooy Kan, and Shmoys [197] provide an extensive treatment of approximation algorithms for the traveling-salesman problem.

Papadimitriou and Steiglitz attribute the algorithm APPROX-VERTEX-COVER to F. Gavril and M. Yannakakis. The vertex-cover problem has been studied extensively (Hochbaum [149] lists 16 different approximation algorithms for this problem), but all the approximation ratios are at least 2 - o(1)

The algorithm APPROX-TSP-TOUR appears in a paper by Rosenkrantz, Stearns, and Lewis [261]. Christofedes improved on this algorithm and gave a 3/2-approximation algorithm for the traveling-salesman problem with the triangle inequality. Arora [21] and Mitchell [223] have shown that if the points are in the euclidean plane, there is a polynomial-time approximation scheme. Theorem 35.3 is due to Sahni and Gonzalez [264].

The analysis of the greedy heuristic for the set-covering problem is modeled after the proof published by Chvátal [61] of a more general result; the basic result as presented here is due to Johnson [166] and Lovász [206].

The algorithm APPROX-SUBSET-SUM and its analysis are loosely modeled after related approximation algorithms for the knapsack and subset-sum problems by Ibarra and Kim [164].

The randomized algorithm for MAX-3-CNF satisfiability is implicit in the work of Johnson [166]. The weighted vertex-cover algorithm is by Hochbaum [148]. Section 35.4 only touches on the power of randomization and linear programming in the design of approximation algorithms. A combination of these two ideas yields a technique called "randomized rounding," in which a problem is first formulated as an integer linear program. The linear-programming relaxation is then solved, and the variables in the solution are interpreted as probabilities. These probabilities are then used to help guide the solution of the original problem. This technique was first used by Raghavan and Thompson [255], and it has had many subsequent uses. (See Motwani, Naor, and Raghavan [227] for a survey.) Several other notable recent ideas in the field of approximation algorithms include the primal dual method (see [116] for a survey), finding sparse cuts for use in divide-and-conquer algorithms [199], and the use of semidefinite programming [115].

As mentioned in the chapter notes for Chapter 34, recent results in probabilistically checkable proofs have led to lower bounds on the approximability of many problems, including several in this chapter. In addition to the references there, the chapter by Arora and Lund [22] contains a good description of the relationship between probabilistically checkable proofs and the hardness of approximating various problems.