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
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"
"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
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
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 <email@example.com>
Latest change August 19, 2003
Technical support: <firstname.lastname@example.org>