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

Bernhard Korte     Jens Vygen

Combinatorial Optimization

Theory and Algorithms

Algorithms and Combinatorics 21
Springer-Verlag, Berlin Heidelberg New York Tokyo Paris Milano

  • First Edition 2000
  • Second Edition 2002
  • Japanese Edition 2005
  • Third Edition 2006
  • Fourth Edition 2008
  • German Edition 2008
  • Second Japanese Edition 2009
  • French Edition 2010
  • Italian Edition 2011
  • Fifth Edition 2012
  • Second German Edition 2012
  • Chinese Edition 2014 (Science Press China)
  • Russian Edition 2015

Preface and Table of Contents (5th edition)

More Information from the publishers:

List of Updates and Errors of the Fifth Edition

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$.
127 36-39 The paper by Dadush, Dey and Vielma [2011] appeared in Mathematical Programming A 145 (2014), 327-348.
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), 765-774.
204 13 Exercise 35 works only for simple graphs.
206 40 The correct page numbers of the paper by Cheung, Lau and Leung [2011] are 197-206.
245 27 The coordinates should be independent.
267 1 Replace k by n.
346 28 Condition (b) should be weakened (for the application in the following proof): we need c(xi)>c(yj) for i<j and c(xi)≥c(yj) for i>j.
347 26 Replace x_1,...,x_l by x_l,...,x_1 and y_0,...,y_{l-1} by y_{l-1},...,y_0.
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), 424-435.
523 37-38,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 30-32 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), 207-214
529 15-20 The proof of the first statement is not entirely clear, but it actually shows the stronger statement that there exists a spanning tree $M$ in $G[S]$ with $\sum_{\{s,t\}\in E(M)} dist_{(Y,c')}(s,t) \le c(E(Y))-c(L)$.
549 30-31 Replace ≤ by ≥ and one δG(A) by δG(B) in both lines.
553 2 Replace 0 by ∅.
554 19-21 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 6-7 The TSP inapproximability bound was improved to 123/122 by Karpinski, Lampis and Schmied [2013]. Reference: Karpinski, M., Lampis, M., Schmied, R. [2013]: New inapproximability bounds for TSP. Algorithms and Computation; Proceedings of ISAAC 2013; LNCS 8283 (L. Cai, S.-W. Chen, T.-W. Lam, eds.), Springer, Berlin 2013, pp. 568-578
591 13-14 The paper by Fiorini et al. [2011] appeared in the Proceedings of the 44th Annual ACM Symposium on Theory of Computing (2012), 95-106.
617 7 "element of" should be "subset of".
627 47-50 The paper by Li [2011] appeared in Information and Computation 222 (2013), 45-58.

Last change: February 19, 2015. Thanks to Maxim Babenko, Steffen Böhmer, Ulrich Brenner, Stephan Held, Stefan Hougardy, Solomon Lo, Jens Maßberg, Jan Schneider, and Sophie Spirkl.