Jens Vygen: [English Homepage] [Deutsche Homepage] [Publications] [Projects] [Students] Textbook [Courses] [Lectures] [Committees]

Bernhard Korte Jens VygenCombinatorial OptimizationTheory and Algorithms
Algorithms and Combinatorics 21 
All entries in the following list refer to the fifth edition. (For a list for the 4th edition, see here.) Any additional comments are welcome.
Page  Line  Comment 

18  41  We assume, w.l.o.g., that E(P) is not a subset of E(Q) (otherwise exchange P and Q). 
32  4  Replace W_1 by v_1. 
32  11  Replace v by v_1. 
124  2  Replace $C=\{...\}$ by $C$. The rows of the matrix $A$ in the Hint are $a_1,...,a_t$. 
186  26  Orlin [2013] found an $O(mn)$time algorithm for the Maximum Flow Problem. Reference: Orlin, J.B. [2013]: Max flows in $O(nm)$ time, or better. Proceedings of the 45th Annual ACM Symposium on Theory of Computing (2013), to appear 
206  40  The correct page numbers of the paper by Cheung, Lau and Leung [2011] are 197206. 
245  27  The coordinates should be independent. 
267  1  Replace k by n. 
362  30  The proof should begin with the following: Without loss of generality, $f(\emptyset) = g(\emptyset)$ and $f(E) = g(E)$. 
371  23  The algorithm finds a maximal element $F$ of $\mathcal{F}$ with $c(F)$ maximum. 
372  13  c should be strictly positive in Exercise 8. 
378  3,2  Replace Ĺ by Φ. Same on page 379, lines 2, 8, and 34, page 381, line 2, page 384, line 31, page 390, lines 4 and 20, page 391, line 18, and page 407, line 3. 
503  14  Replace $O(E(H))$ by $O(\log E(H))$. 
519  4  The paper by Kawarabayashi, Kobayashi and Reed [2010] appeared in the Journal of Combinatorial Theory B 102 (2012), 424435. 
523  3738,40  The definition of $q(U\cup\{x\},x)$ is not good, as Lemma 20.4(a) may not hold in general. To fix this, one can either require (w.l.o.g.) $c$ to be a metric or, easier, redefine $q$ as follows: $q(U\cup\{x\},x) := \min \{ c(E(S'))+c(E(S'')) : \emptyset \not= U'\subset U, S' is a Steiner tree for U'\cup\{x\} in G, S'' is a Steiner tree for (U\setminus U')\cup\{x\} in G \}$. Then (a) is trivial, and the proof of (b) is essentially unchanged. 
526  3032  The Steiner tree inapproximability bound was improved to 1.01 by Chlebík and Chlebíková [2008]. Reference: Chlebík, M., and Chlebíková, J.: The Steiner tree problem on graphs: Inapproximability results. Theoretical Computer Science 406 (2008), 207214 
554  1921  The paper by Byrka et al. [2010] appeared in the Journal of the ACM 60 (2013), Article 6, with the title: Steiner tree approximation via iterative randomized rounding. 
562  67  The TSP inapproximability bound was improved to 185/184 by Lampis [2012]. Reference: Lampis, M. [2012]: Improved inapproximability for TSP. Approximation, Randomization, and Combinatorial Optimization; Proceedings of the 16th APPROX Workshop 2012; LNCS 7408 (A. Gupta, K. Jansen, J. Rolim, R. Servedio, eds.), Springer, Berlin 2012, pp. 243253 
591  1314  The paper by Fiorini et al. [2011] appeared in the Proceedings of the 44th Annual ACM Symposium on Theory of Computing (2012), 95106. 
617  7  "element of" should be "subset of". 
627  4750  The paper by Li [2011] appeared in Information and Computation 222 (2013), 4558. 
Last change: March 28, 2014. Thanks to Steffen Böhmer, Ulrich Brenner, Stephan Held, Stefan Hougardy, Jens Maßberg, and Jan Schneider.