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 (Moscow Center for Continuous Mathematical Education)
  • Second French Edition 2018
  • Sixth Edition 2018
  • Third German Edition 2018
Preface and Table of Contents (6th edition)

More Information from the publishers:


List of Updates and Errors of the Sixth Edition

All entries in the following list refer to the sixth edition. (For an outdated list for the 5th edition, see here.) Any additional comments are welcome.

Page Line Comment
58 14 Replace "min" by "max".
204 24 One must require $c \ge c'$ in Exercise 6.
303 25-27 The full version of the paper by Gabow [1990] appeared in ACM Transactions on Algorithms 14 (2018), Article 39.
324 1-3 The full version of the paper by Gabow [1983] appeared in ACM Transactions on Algorithms 14 (2018), Article 39.
378 10 The right-hand side of this inequality should be $\max \{ \sum_{t=(p,A,B)\in T_{i-1}} p x_t \Delta_B, \sum_{t=(p,A,B)\in T_{i-1}} p (1-x_t) \Delta_A \}$. This is sufficient because either $\Exp[f(O_{i-1})-f(O_i)] \le x_t \Delta_B$ for all $(p,A,B)\in T_{i-1}$ or $\Exp[f(O_{i-1})-f(O_i)] \le (1-x_t) \Delta_A$ for all $(p,A,B)\in T_{i-1}$; see the proof of (14.4).
379 38 In Exercise 11,  f  should be integer-valued.
381 30 Replace "$f$ and any $g_C$" by "$g$ and any $f_C$".
382 26-28 The paper by Buchbinder and Feldman [2016] appeared in ACM Transactions on Algorithms 14 (2018), Article 14.
434 3 A factor 1/2 is missing on the left-hand side of the inequality.
533 29 This line should read: "Set $E(G):=\delta_{G'}(X)$ and $E(H):=E(G')\setminus\delta_{G'}(X)$."
552 13 Replace G+f by G[T]+f.
573/574 19/25 Lemma 20.38 and Theorem 20.39 also hold when f can have negative values (which can happen when we apply the Theorem).
628 28-29 The paper by Svensson, Tarnawski and Végh [2017] appeared in the Proceedings of the 50th Annual ACM Symposium on Theory of Computing (2018), pp. 204-213.
628 30-32 The paper by Traub and Vygen [2018] appeared in the Journal of the ACM 66 (2019), Article 14.

Last change: March 26, 2019. Thanks to Ulrich Brenner, Solomon Lo, Rabe von Randow, Rudolf Scheifele, Jannik Silvanus, Vera Traub, Shi-Chun Tsai, Dingwen Yuan, and all people reporting errors in the future!