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 (forthcoming soon)
  • Chinese Edition forthcoming
  • Russian Edition in preparation

Preface and Table of Contents (5th edition)

More Information from the publishers:

List of Updates and Errors of the Fourth Edition

The following list refers to the fourth edition and is not maintained anymore. All changes (and many more) are included the fifth edition. There is a new list for the fifth edition; so any additional comments are welcome.

Page Line Comment
18 20 In Theorem 2.5 (f), replace "path" by "walk".
41 3 $J_{e^*}$ and $J_e$ must cross (i.e., if $e^*$ is a loop, the face bounded by $J_{e^*}$ must contain exactly one endpoint of $e$).
54 3-4 It is possible to choose a and A' as required (for example by considering a face of dimension n+1-rank(A)), but this is not trivial.
60 22 Replace "-c" by "-b".
62 6,10 Z must be nonempty. In the beginning of the proof replace "There is a $z\in Z$" by "There is a $z\in conv(Z)$".
62 14 Replace "A'\leq b' " by "A'x\leq b' ".
68 20 Replace "$a \in \mathbb{R}^n$ with $a^T x < a^T y$" in Exercise 20(b) by "$a \in \mathbb{R}^n\setminus\{0\}$ with $a^T x \leq a^T y$".
78 13,17,19 Replace $z_{ir}$, $z_{ik}$, and $z_{kk}$, respectively, by the values of these variables before the inner loop.
91 12 Replace "E_0" by "volume(E_0)".
100 24-25 We should not (and do not need to) assume $x$ or $\lambda_i,\mu_i$ to be rational. The result follows from writing $$x = \sum_{i=1}^l \frac{\mu_1}{l} (\lfloor r_i \rfloor + 1 - r_i) (z_1 + \lfloor r_i \rfloor y_i) + \sum_{i=1}^l \frac{\mu_1}{l} (r_i - \lfloor r_i \rfloor) (z_1 + (\lfloor r_i \rfloor + 1) y_i) + \sum_{i=2}^m \mu_i z_i,$$ where $r_i := \frac{l \lambda_i}{\mu_1}$.
103 18,25 Replace 12 by 13.
131 4-5 It is true but not obvious that (c) holds. However, the following condition obviously holds, which also implies optimality very similarly to the proof of (c)\impl (a) in Theorem 6.2: We can order $E(T)=\{e_1,\ldots,e_{n-1}\}$ such that for each $i\in\{1,\ldots,n-1\}$ there exists a set $X\subseteq V(G)$ such that $e_i$ is a minimum cost edge of $\delta(X)$ and $e_j\notin\delta(X)$ for all $j\in\{1,\ldots,i-1\}$.
134 15 Replace "$K=2\sum_{e\in E(G)}|c(e)|$" by "$K=1+\sum_{e\in E(G)}|c(e)|$".
137 4 Replace = by ≤.
155 26-27 Klein, Mozes and Weimann found an $O(n \log^2 n)$-time algorithm for planar digraphs. Reference: Klein, P.N., Mozes, S., and Weimann, O. [2010]: Shortest paths in directed planar graphs with negative lengths: a linear-space $O(n\log^2 n)$-time algorithm. ACM Transactions on Algorithms 6 (2010), Article 30
157 26-27 Corollary 7.11 is proved only for digraphs with conservative weights and undirected graphs with nonnegative weights.
163 27-28 The paper by Chan [2007} appeared in SIAM Journal on Computing 39 (2010), 2075-2089
195 8-10 The paper by Borradile and Klein [2006] appeared in the Journal of the ACM 56 (2009), Article 9.
204 30 Replace "$H$ is a subgraph" by "Every simple subgraph of $H$ is a subgraph". Same on page 205, line 8.
221 15 Replace $E^+_G(X,\{y\})$ by $E^+_G(X\setminus\{y\},\{y\})$.
250 39 Replace "symmetric" by "anti-symmetric".
252 8,13 This algorithm was discovered independently by Karzanov [1973].
268 19,20,22-25 In each of these six lines, the $\rho$-pointer should refer to the base of the previously outermost blossom: replace $\rho^{k_{x_{2i}}}(x_{2i})$ by $\rho^{k_{x_{2i}}-1}(x_{2i})$ etc.
270/271 3/8 Replace "x_{\{c\}}" by "z_{\{c\}}".
270 13 Replace "$\tau_v^A=d$" by "$\tau_d^A=c$".
275 35-36 A new implementation by Kolmogorov seems to be faster. Reference: Kolmogorov, V. [2009]: Blossom V: a new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation 1 (2009), 43-67
299 20-22 This result was improved and simplified by Letchford, Reinelt and Theis. Reference: Letchford, A.N., Reinelt, G., and Theis, D.O.: Odd minimum cut sets and $b$-matchings revisited. SIAM Journal on Discrete Mathematics 22 (2008), 1480-1487
320 14 Replace "$r:E\to\mathbb{Z}_+$" by "$r:2^E\to\mathbb{Z}_+$".
330 31-32 We need a stronger version of Lemma 13.28 here. The following generalizes Lemma 13.27 and suffices: Let $(E,\Fscr)$ be a matroid, $c:E \to \mathbb{R}$, and $X\in\Fscr$. Let $x_1,...,x_l \in X$ and $y_1,...,y_l \notin X$ with (a) $x_j \in C(X, y_j)$ and $c(x_j) = c(y_j)$ for $j = 1,...,l$, and (b) $x_i \notin C(X,y_j)$ or $c(x_i) > c(y_j)$ for $1\le i,j \le l$ with $i\not=j$. Then $(X \setminus \{x_1,...,x_l}) \cup \{y_1,...,y_l\} \in \Fscr$.
339 1 Replace "(c)" by "the anti-exchange property".
355 29 A new survey paper appeared: Iwata, S. [2008]: Submodular function minimization. Mathematical Programming B 112 (2008), 45-64
357 1-4 The paper by Orlin [2007] appeared in Mathematical Programming 118 (2009), 237-251
370 12 Replace p(size(x)) by p(size(y)). Same on page 372, line 5.
391 40-41 The paper by Fürer [2007] appeared in SIAM Journal on Computing 39 (2009), 979-1005
420 21 The approximation ratio was improved to 1.256 by Avidor, Berkovitch and Zwick [2006]. Reference: Avidor, A., Berkovitch, I., and Zwick, U. [2006]: Improved approximation algorithms for MAX NAE-SAT and MAX SAT. Approximation and Online Algorithms - Proceedings of the 3rd WAOA workshop (2005); LNCS 3879 (Erlebach, T., Persiano, G., eds.), Springer, Berlin 2006, pp. 27-40
437 19-21 The paper by Sanders and Steurer [2005] appeared in ACM Transactions on Algorithms 4 (2008), Article 21
437 37-39 The paper by Zuckerman [2006] appeared in Theory of Computing 3 (2007), 103-128.
453 10 The bound of 7/4 by Simchi-Levi [1994] was improved to 12/7 by Xia and Tan [2010]. Reference: Xia, B., and Tan, Z. [2010]: Tighter bounds of the First Fit algorithm for the bin-packing problem. Discrete Applied Mathematics 158 (2010), 1668-1675
454 7 This bound was improved to $\frac{11}{9}OPT(I)+\frac{2}{3}$ by Dósa. Reference: Dósa, G. [2007]: The tight bound of first fit decreasing bin-packing algorithm is $FFD(I) \le11/9 OPT(I)+6/9$. In: Combinatorics, Algorithms, Probabilistic and Experimental Methodologies; LNCS 4614 (Chen, B., Paterson, M., Zhang, G., eds.), Springer, Berlin 2007, pp. 1-11
462 34 Replace "linear time" by "O(n log n) time" in Exercise 2.
463 1-2 Exercise 5 should read: Show that there is no online algorithm for the Bin-Packing Problem with performance ratio less than 4/3 (regardless of the running time).
486 last Replace "for all $X\subseteq V(G)$" by "for all $\emptyset\not=X\subset V(G)$".
488 33-35 The paper by Garg and Könemann [1998] appeared in SIAM Journal on Computing 37 (2007), 630-652
488 41-43 The paper by Karakostas [2002] appeared in ACM Transactions on Algorithms 4 (2008), Article 13
495 18 An even faster algorithm (for many terminals) was found by Vygen [2009]. Reference: Vygen, J.: Faster algorithm for optimum Steiner trees. Technical Report No. 091003, Research Institute for Discrete Mathematics, University of Bonn, 2009. Information Processing Letters, to appear
496 31 Byrka et al. [2010] found a $1.39$-factor approximation algorithm for the Steiner tree problem. Reference: Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L. [2010]: An improved LP-based approximation for Steiner tree. Proceedings of the 42th Annual ACM Symposium on Theory of Computing (2010), 583-592
497 6-9 In the definition of $k$-restricted graphs, the following condition is missing: the graph arising from $(\{(i,v): i=1,...,t,v\in V(Y_i)\}, \{\{(i,v),(i,w)\}: i=1,...,t,\{v,w\}\in E(Y_i)\})$ by contracting the set $\{i: v\in V(Y_i)\}\times\{v\}$ for each $v\in T$ must be connected.
501 4 Replace $Y^*_k$ by $Y^*$.
523 27-29 An improved version of the paper by Borradile, Kenyon-Mathieu and Klein [2007] appeared in Borradile, G., Klein, P., and Kenyon, C.: An O(n log n) approximation scheme for Steiner tree in planar graphs, ACM Transactions of Algorithms 5 (2009), Article 31.
524 4-5 The paper by Fuchs et al. [2007] appeared in Theory of Computing Systems 41 (2007), 493-500.
524 12-14 The paper by Gabow et al. [2005] appeared in Networks 53 (2009), 345-357.
533 9 Formally, V' may not be well-rounded because its diameter may be larger than 64|V'|/ε. However, all other statements remain true.
555 3 Replace "new" by "original".
557 12-13 Feige and Singh [2007] found a $(\frac{2}{3}\log n)$-factor approximation algorithm for the asymmetric TSP. Asadpour et al. [2010] found a randomized algorithm that finds a solution within a factor of O(log n / log log n) of the optimum with high probability. References: Feige, U., and Singh, M. [2007]: Improved approximation algorithms for traveling salesperson tours and paths in directed graphs. Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems; LNCS 4627 (M. Charikar, K. Jansen, O. Reingold, J.D.P. Rolim, eds.), Springer, Berlin 2007, pp. 104-118. Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., and Saberi, A. [2010]: An $O(\log n/\log\log n)$-approximation algorithm for the asymmetric traveling salesman problem. Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (2010), 379-389
561 21-23 The paper by Klein [2005] appeared in SIAM Journal on Computing 37 (2008), 1926-1952
568 32 When setting $X:=X\cup\{i\}$ one should also set $\sigma(j):=i$ for $j\in D$ with $v_j>c_{ij}$.
569 27 Replace "the budget of $j$" by "$t$".
570 12 Replace $\tau$ by $t$.
570 15 Replace "$\sigma(j):=i$" by "$\sigma(j):=i$, $v_j:=t$ and $U:=U\setminus\{j\}$".
579 22 Zhang [2007] found a 3.733-factor approximation algorithm for the metric $k$-facility location problem. Reference: Zhang, P. [2007]: A new approximation algorithm for the $k$-facility location problem. Theoretical Computer Science 384 (2007), 126-135
595 26 To make Exercise 7 nontrivial, the facility costs should be included in the objective function.
597 8-11 The paper by Byrka [2007] appeared in SIAM Journal on Computing 39 (2010), 2212-2231 with K. Aardal as co-author.
598 15-18 The paper by Zhang Chen and Ye [2004] appeared in Mathematics of Operations Research 30 (2005), 389-403
600 3 Replace "length of the shortest $x$-$y$-path" by "length of a shortest $v$-$w$-path".

Last change: August 26, 2011. Thanks to Takao Asano, Benjamin Bolten, Christoph Buchheim, Jean Fonlupt, Michael Gester, Stephan Held, Stefan Hougardy, Hiroshi Iida, Klaus Jansen, Alexander Karzanov, Alexander Kleff, Niko Klewinghaus, Stefan Knauf, Barbara Langfeld, Jens Maßberg, Marc Pfetsch, Klaus Radke, Rabe von Randow, Tomás Salles, Jan Schneider, Christian Schulte, Martin Skutella, and Simon Wedeking.