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. 
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. 
Last change: January 25, 2019. Thanks to Ulrich Brenner, Rabe von Randow, Rudolf Scheifele, Jannik Silvanus, Vera Traub, ShiChun Tsai, Dingwen Yuan, and all people reporting errors in the future!