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 

58  14  Replace "min" by "max". 
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. 
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  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: March 26, 2019. Thanks to Ulrich Brenner, Solomon Lo, Rabe von Randow, Rudolf Scheifele, Jannik Silvanus, Vera Traub, ShiChun Tsai, Dingwen Yuan, and all people reporting errors in the future!