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.