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

Bernhard Korte Jens VygenCombinatorial OptimizationTheory and Algorithms
Algorithms and Combinatorics 21 
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 

38  24  Replace 1958 by 1758. 
58  14  Replace "min" by "max". 
138  35  Replace $k \ge 1$ by $k \ge 2$. 
141  9  Replace c(e):=0 by c'(e):=0. 
153  1316  The inequality system in Exercise 20 is not correct. A correct version is: $x_e\ge 0$ ($e\in E(G)$), $z_{r,u,v}\ge 0$ ($\{u,v\}\in E(G), r\in V(G)$), $\sum_{e\in E(G)}x_e=n1$, $x_e=z_{r,u,v}+z_{r,v,u}$ ($e=\{u,v\}\in E(G)$, $r\in V(G)$), and $\sum_{\{u,v\}\in\delta(v)} z_{r,u,v}=1$ ($v\in V(G)$, $r\in V(G)\setminus \{v\}$). 
169  34  Replace arborescence by tree. 
204  24  One must require $c \ge c'$ in Exercise 6. 
289  39  Replace $\sigma(\rho^{k_v}(v)):=r_j$ by $\sigma(\rho^{k_v1}(v)):=r_j$. 
291  10  Replace $\epsilon_3=0$ by $\epsilon_2=0$. 
303  2527  The full version of the paper by Gabow [1990] appeared in ACM Transactions on Algorithms 14 (2018), Article 39. 
324  13  The full version of the paper by Gabow [1983] appeared in ACM Transactions on Algorithms 14 (2018), Article 39. 
351  30,31  Repolace $X$ by $X_k$. 
354  31  Rep[lace "r(X)=" by "r'(X)=". 
360  33  We need $y\not= z$ here. 
378  10  The righthand side of this inequality should be $\max \{ \sum_{t=(p,A,B)\in T_{i1}} p x_t \Delta_B, \sum_{t=(p,A,B)\in T_{i1}} p (1x_t) \Delta_A \}$. This is sufficient because either $\Exp[f(O_{i1})f(O_i)] \le x_t \Delta_B$ for all $(p,A,B)\in T_{i1}$ or $\Exp[f(O_{i1})f(O_i)] \le (1x_t) \Delta_A$ for all $(p,A,B)\in T_{i1}$; see the proof of (14.4). 
379  32  In Exercise 10, one must require $f(\emptyset)=0$. 
379  38  In Exercise 11, f should be integervalued. 
381  30  Replace "$f$ and any $g_C$" by "$g$ and any $f_C$". 
382  2628  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 lefthand side of the inequality. 
460  2122  The halfsentence "which is better..." makes no sense and should be deleted. 
480  7  Replace (U,V,W,T) by (P,Q,R,T). 
485  3  The second sum should go from 1 to h1. 
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. 
557  21  We can choose $Y^*_k$ to be an optimum Steiner tree here. 
558  13  The second sum should of course go over $C\in\delta^+_{\mathcal{C}^k}(U)$. 
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). 
584  33  We set $x'_e:=\frac{1}{1\alpha}x_e$. 
628  2829  The paper by Svensson, Tarnawski and Végh [2017] appeared in the Journal of the ACM 67 (2020), Article 37. 
628  3032  The paper by Traub and Vygen [2018] appeared in the Journal of the ACM 66 (2019), Article 14. 
630  2930  "greater than 1" should be replaced by "greater than 2". 
Last change: April 30, 2023. Thanks to Takao Asano, Jannis Blauth, Lukas Bonfert, Ulrich Brenner, Marc Goerigk, Stephan Held, Felix Horchler, Solomon Lo, Stefan Rabenstein, Rabe von Randow, Rudolf Scheifele, Jannik Silvanus, Vera Traub, ShiChun Tsai, Dingwen Yuan, and all people reporting errors in the future!