Errata to Complexity and Approximation

Here is a list of the errors in the first edition of the book that have been reported. For the sake of completeness we also maintain a list of minor errors.

If you want to report a new error, please use the error reporting web form.

The authors are grateful to the following persons that have reported errors:
Joachim Gudmundsson, Amit Kagan, Jochen Konemann, Jan Korst, Jan van Leeuwen, Daniel Lehmann, Elena Lodi.

Page 46, line 14

The proof of theorem 2.6 can be improved by changing "the number of vertices that belong to some optimal solution" to "the number of edges that are incident to vertices of some optimal solution".
Corrected version of page 46.

Page 49, line 14

In the proof of lemma 2.4 "for j=1,2,..." should be changed to "for j=0,1,...".
Corrected version of page 49.

Page 54, line 2

In the definition of Problem 2.4 Minimum Bin Packing "set" should be changed to "multiset".
Corrected version of page 54.

Page 57, line -10

On page 57, it is mentioned that for Minimum Bin Packing the results of Best Fit Decreasing are at least as good as those of First Fit Decreasing. Proving this is left as an exercise to the reader (Exercise 2.9). The following instance shows that this is not true: B = 27 (bin size) itemsizes: 20, 11, 11, 4, 3, 3, 2. For this instance, FFD uses exactly two bins, while BFD uses three.
Corrected version of page 57.

Page 59, line 9

The left-hand side of Equation (2.6) should be "kn" instead of "ki".
Corrected version of page 59.

Page 68, line 1

"optimal value of P" should be "optimal value of LP" on line 1.
Corrected version of page 68.

Page 71, Program 2.8

"si" should be "ai" on line 7 of the program.
"S*(1,p)" should be "S*(1,0)" on line 9 of the program.
"s1" should be "a1" on line 10 of the program.
Corrected version of page 71.

Page 72, line 8

In the statement "x':= instance with profits..." in Program 2.9 the floor operation should be taken just of "p'i/2t".
Corrected version of page 72.

Page 80, Exercise 2.9

A counter example can be found. See the error on page 57, line -10.
Corrected version of page 80.

Page 99, line 6 of Example 3.3

The figure identifier is missing. Correction: the approximate tour shown in figure 3.4(a) results.
Corrected version of page 99.

Page 166, line 5

A beta is missing after greater than or equal sign.
Corrected version of page 166.

Page 430, Problem SR1

Error in the definition of the problem Minimum Bin Packing. Remove "such that the sum of the a partition of U".
Corrected version of page 430.

Page 434, Problem SR10

The definition of the problem Minimum Rectangle Cover is wrong. It should be:

INSTANCE: An arbitrary polygon P.
SOLUTION: A collection of m rectangles whose union is exactly equal to the polygon P.
MEASURE: Size, i.e. number m of elements, of the collection.
Corrected version of page 434.

Page 482, line -5

The volume of Information Processing Letters that published the article Relative complexity of evaluating... should be 33.

Errata to the CD

Error in JAZ command line

On the CD the command starting JAZ is given (in jaz.html), but on the command line the character that looks like a dash is in fact not a dash, even though it should be. The correct command line is the following:

      java -cp JAZ.jar JazPMenuBar

Up to the web site of the book.

Responsible for this page: Viggo Kann <>
Latest change August 19, 2003
Technical support: <>