Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

List of known errors (last updated: Feb 28, 2013)

Page Location Description
14 Line -6 The word transfered should be transferred
17 Paragraph containg third equation The first sentence of the paragraph should start as follows: "Among all nonnegative solutions of these equations and inequalities..."
29 Line 10 of second paragraph The number 452.5 should be 452.25
75 First sentence after first LP The sentence should start as "We want to stress that..."
91 Line 2 yTb0 should be yTb≥0 (non-bold zero)
96 Paragraph after Lemma 6.5.3 The set {tx: x ∈ D} should be {tx: x∈ D, t ≥ 0}
104 Line before equation The words "an m x m matrix M with all entries nonnegative" should be replaced by "a nonnegative matrix M with m columns".
111 The first two equations In the first equation, the fraction Qsk / √skT Q sk should be replaced by Qkai / √aiT Qk ai. In the second equation, the fraction QskskTQ / skTQsk should accordingly be replaced by QkaiaiTQk / aiTQkai.
112 First sentence of last paragraph The sentence should start as "If, for example, all the aij and bi are integers..."
115, 116 Line 2 of 7.2, Line 2 of p.116 Narendra Karmarkar's last name is misspelled as "Karmakar". Also, Karmarkar was a researcher at AT & T Bell Laboratories when he invented his algorithm, not at IBM.
120 End of first paragraph The conditions that are given on f and the gi are in general not sufficient for the existence of Lagrange multipliers. The paragraph should continue as follows: "But the problem max x: x2=0 shows that in general, additional conditions on x are needed. A sufficient condition is that the vectors ∇g1(x),∇g2(x),...,∇gm(x) are linearly independent. However, if all the gi are linear functions (as in our case), it is easy to see that this extra condition is redundant."
126 Last line The word nontrivial should be removed
127 Equation defining M0 In the third line of the matrix defining M0, it should be bT and cT instead of b and c
167 Paragraph on Sparse solutions of underdetermined linear systems In Line 4, the subordinate clause "the rows of A form a basis of its orthogonal complement" should read as "the rows of A lie in its orthogonal complement". Then the following sentence should be inserted: "In our application, A will have full rank and thus form a basis of the orthogonal complement".
182 Last line In the inequality, the function ν* should be replaced by τ*.
219 14th entry of right column "Karmakar's algorithm" should be "Karmarkar's algorithm".