The authors describe this survey as a small textbook, and I agree wholeheartedly. But, it is a textbook summarizing about 80 related papers in 41 pages, so the interested reader is required to read it slowly, and with a lot of thought. Nevertheless, the guidance provided is excellent.

The paper primarily considers graph-theoretic and set-theoretic problems. Most of the problems are nondeterministic polynomial time (NP) hard, although pedagogy may have demanded that a few other problems be addressed by the very generalized methods the authors use, to tie a wide range of optimization problems together under one model. An r-approximate algorithm for the solution of an optimization problem is defined as one that yields a solution whose value is within a factor r of the optimal cost (r will be greater than 1 for minimization problems and less than 1 for maximization problems). Local ratio algorithms apply in the case where a solution can be represented by a vector, and the solution’s cost can be represented by the scalar product of the solution vector and a “weight vector” gleaned from the problem. The representation of a problem in this form is where the ingenuity of the designer is required.

Many graph problems are classified into the general class of “graph editing” problems. The authors address solutions of partial problems whose weight and solution vectors can be seen as the sum of two partial weight and solution vectors. The local ratio theorem shows that, if the partial solutions are r-approximate, then so is their sum.

The authors present a generic r-approximate solution as consisting of the recursion of a three-way “if-then” algorithm, with the three “then” parts of the algorithm called weight decomposition, problem reduction, and optimum solution.

The above concepts and their applications are illustrated using many examples. The examples are used to introduce the concepts, and also to illustrate their application in a step-by-step manner. The authors discuss the challenges associated with the application of the model as they arise, and illustrate the way the challenges are met.

In my experience, most approximate algorithms are described in the literature as being developed on an ad hoc basis for a specific problem. This survey is a laudable effort toward tying them into a uniform approach, and will be appreciated by disciplined and dedicated readers.