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

Bernhard Korte 
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  34  It is possible to choose a and A' as required (for example by considering a face of dimension n+1rank(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  2425  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  45  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_{n1}\}$ such that for each $i\in\{1,\ldots,n1\}$ 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,i1\}$. 
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  2627  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 linearspace $O(n\log^2 n)$time algorithm. ACM Transactions on Algorithms 6 (2010), Article 30 
157  2627  Corollary 7.11 is proved only for digraphs with conservative weights and undirected graphs with nonnegative weights. 
163  2728  The paper by Chan [2007} appeared in SIAM Journal on Computing 39 (2010), 20752089 
195  810  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 "antisymmetric". 
252  8,13  This algorithm was discovered independently by Karzanov [1973]. 
268  19,20,2225  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  3536  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), 4367 
299  2022  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), 14801487 
320  14  Replace "$r:E\to\mathbb{Z}_+$" by "$r:2^E\to\mathbb{Z}_+$". 
330  3132  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 antiexchange property". 
355  29  A new survey paper appeared: Iwata, S. [2008]: Submodular function minimization. Mathematical Programming B 112 (2008), 4564 
357  14  The paper by Orlin [2007] appeared in Mathematical Programming 118 (2009), 237251 
370  12  Replace p(size(x)) by p(size(y)). Same on page 372, line 5. 
391  4041  The paper by Fürer [2007] appeared in SIAM Journal on Computing 39 (2009), 9791005 
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 NAESAT 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. 2740 
437  1921  The paper by Sanders and Steurer [2005] appeared in ACM Transactions on Algorithms 4 (2008), Article 21 
437  3739  The paper by Zuckerman [2006] appeared in Theory of Computing 3 (2007), 103128. 
453  10  The bound of 7/4 by SimchiLevi [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 binpacking problem. Discrete Applied Mathematics 158 (2010), 16681675 
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 binpacking 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. 111 
462  34  Replace "linear time" by "O(n log n) time" in Exercise 2. 
463  12  Exercise 5 should read: Show that there is no online algorithm for the BinPacking 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  3335  The paper by Garg and Könemann [1998] appeared in SIAM Journal on Computing 37 (2007), 630652 
488  4143  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 LPbased approximation for Steiner tree. Proceedings of the 42th Annual ACM Symposium on Theory of Computing (2010), 583592 
497  69  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  2729  An improved version of the paper by Borradile, KenyonMathieu 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  45  The paper by Fuchs et al. [2007] appeared in Theory of Computing Systems 41 (2007), 493500. 
524  1214  The paper by Gabow et al. [2005] appeared in Networks 53 (2009), 345357. 
533  9  Formally, V' may not be wellrounded because its diameter may be larger than 64V'/ε. However, all other statements remain true. 
555  3  Replace "new" by "original". 
557  1213  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. 104118. 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 ACMSIAM Symposium on Discrete Algorithms (2010), 379389 
561  2123  The paper by Klein [2005] appeared in SIAM Journal on Computing 37 (2008), 19261952 
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.733factor 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), 126135 
595  26  To make Exercise 7 nontrivial, the facility costs should be included in the objective function. 
597  811  The paper by Byrka [2007] appeared in SIAM Journal on Computing 39 (2010), 22122231 with K. Aardal as coauthor. 
598  1518  The paper by Zhang Chen and Ye [2004] appeared in Mathematics of Operations Research 30 (2005), 389403 
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.