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  Replave 1958 by 1758. 
58  14  Replace "min" by "max". 
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\}$). 
204  24  One must require $c \ge c'$ in Exercise 6. 
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. 
354  31  Rep[lace "r(X)=" by "r'(X)=". 
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. 
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  2829  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. 204213. 
628  3032  The paper by Traub and Vygen [2018] appeared in the Journal of the ACM 66 (2019), Article 14. 
Last change: January 30, 2020. Thanks to Lukas Bonfert, Ulrich Brenner, Stephan Held, 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!