Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

List of known errors (last updated: August 19, 2013)

Page Location Description
5 Line -5 before What is Polynomial Time? The comma after the word algorithms should not be separated from the word by a space
34 First equation, last term on the left-hand side uj should be vj, and uj' should be vj'.
37 Line 5 The variable t should be from R+ rather than from Rn+
82 Line 2 of Lemma 5.3.5 The number of feasibility problems to be solved should be log 1/ε + 1 instead of log 1/ε (where the logarithm is binary)
88 Line 3 of Proposition 5.5.6 "Then, for all k=1,2,.." should be "Then, for all k=2,3,..."
95 First equation In the second term, the second quotient should be g2k+1/g2k instead of g2k/g2k+1
117 Exercise 6.2 In the claimed expression for gij, the ∇ symbol in the numerator should be removed
144 8.3.25 +ε should be -ε
146 8.3.31 The left hand side of the inequality should be divided by |E|
147 8.3.37, line 4 of third bullet The part "...disk Dq centered at q..." should read as "...disk Dq centered at q and disjoint from C..."
158 9.1.11 The upper bound on the required number of colors was further decreased by Kawarabayashi and Thorup in 2012
159 Second º bullet It is known at least since 1996 that vector and strict vector chromatic number may differ. An example can be found in Theorem 6.1.3. of the following diploma thesis: Clemens Gröpel, Über Approximationsalgorithmen zur Färbung k-färbbarer Graphen, die vektorchromatische Zahl und andere Varianten der Theta-Funktion, Humbold-University Berlin, 1996.
160 9.3.2, second º bullet The "3" should be in the numerator, not in the denominator.
166 Second-to-last line The word "with" should be removed
175 10.4.7 There is a mistake in the calculation with the constants; the square root of 1/10 should have been taken, and this would spoil the result. A possible fix is to write 1/30 instead of 1/10 in the chain of inequalities in the fifth bullet of 10.4.6 (which is valid, just by a more precise calculation with the constants) and then have 2/√ 30 instead of the first 1/5 and 2/30 instead of the second one, which works. The factor of 2 in front of RA can actually be dropped with a bit more care.
177 Line 1 The sentence should end as "...for which the correlation is at least 1/3 of the correlation of an optimal clustering."
201 12.3.10, second bullet The sentence should end as " most 90o." instead of " least 90o."
201 12.3.10, third bullet The inequality in the equation should be reversed, i.e. ≥ instead of ≤
225 13.3.31, second bullet ...for all i,j... should be replaced by ...for all i≠j...
234 tenth-to-last line The set {-1,1} should be {-1,1}d