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 fifth edition. (For a list for the 4th edition, see here.) Any additional comments are welcome.
Page  Line  Comment 

18  41  We assume, w.l.o.g., that E(P) is not a subset of E(Q) (otherwise exchange P and Q). 
32  4  Replace W_1 by v_1. 
32  11  Replace v by v_1. 
124  2  Replace $C=\{...\}$ by $C$. The rows of the matrix $A$ in the Hint are $a_1,...,a_t$. 
127  3639  The paper by Dadush, Dey and Vielma [2011] appeared in Mathematical Programming A 145 (2014), 327348. 
137  1415  During DELETEMIN, one should take only vertices $u$ with $\delta^(u)=\emptyset$ into consideration. 
163  17  Chan's running time was improved by Han and Takaoka [2016] to $O(n^3 \log\log n / \log^2 n)$. Reference: Han, Y., and Takaoka, T. [2016]: An O(n^3 log log n / log^2 n) time algorithm for all pairs shortest paths. Journal of Discrete Algorithms 3841 (2016), 919 
186  26  Orlin [2013] found an $O(mn)$time algorithm for the Maximum Flow Problem. Reference: Orlin, J.B. [2013]: Max flows in $O(nm)$ time, or better. Proceedings of the 45th Annual ACM Symposium on Theory of Computing (2013), 765774. 
197  47  Kawarabayashi and Thorup [2015] showed how to determine the edgeconnectivity of a given graph in $O(m\log^{12}n)$ time. Reference: Kawarabayashi, K., and Thorup, M. [2015]: Deterministic global minimum cut of a simple graph in nearlinear time. Proceedings of the 47th Annual ACM Symposium on Theory of Computing (2015), 665674. 
204  13  Exercise 35 works only for simple graphs. 
206  40  The correct page numbers of the paper by Cheung, Lau and Leung [2011] are 197206. 
225  11  Replace "each by less than 2γ" by "adding up to less than 2γ(n1)". 
245  27  The coordinates should be independent. 
267  1  Replace k by n. 
268  2630  Exercise 26 does not work; it is not clear how to update $\varphi$ fast enough. 
298  4143  A full version of Gabow's [1990] paper was published on arXiv:1611.07541. 
346  28  Condition (b) should be weakened (for the application in the following proof): we need c(x_{i})>c(y_{j}) for i<j and c(x_{i})≥c(y_{j}) for i>j. 
347  26  Replace x_1,...,x_l by x_l,...,x_1 and y_0,...,y_{l1} by y_{l1},...,y_0. 
362  30  The proof should begin with the following: Without loss of generality, $f(\emptyset) = g(\emptyset)$ and $f(E) = g(E)$. 
369  14  Lee, Sidford and Wong [2015] found a strongly polynomialtime algorithm that minimizes a submodular function in $O(\gamma n^3 \log^2 n + n^4 \log^{O(1)} n)$ time. Reference: Lee, Y.T., Sidford, A., and Wong, S.C.: A faster cutting plane method and its implications for combinatorial and convex optimization. Proceedings of the 56th Annual Symposium on Foundations of Computer Science (2015), to appear 
371  23  The algorithm finds a maximal element $F$ of $\mathcal{F}$ with $c(F)$ maximum. 
372  13  c should be strictly positive in Exercise 8. 
378  3,2  Replace Ĺ by Φ. Same on page 379, lines 2, 8, and 34, page 381, line 2, page 384, line 31, page 390, lines 4 and 20, page 391, line 18, and page 407, line 3. 
457  2931  The paper by Singh and Lau appeared in the Journal of the ACM 62 (2015), Article 1. 
475  39  Dósa and Sgall [2013] improved upper and lower bound of Theorem 18.6 to $\lfloor\frac{17}{10}OPT(I)\rfloor$. Reference: Dósa, G. and Sgall, J.: First fit bin packing: a tight analysis. Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (2013), 538549 
486  3639  The full version of the paper by Dósa [2007] appeared as follows: Dósa, G., Li, R., Han, X., and Tuza, Z.: Tight absolute bound for First Fit Descreasing binpacking: $\textsl{FFD}(L)\le 11/9\, \textsl{OPT}(L) + 6/9$. Theoretical Computer Science 510 (2013), 1361 
499  23  Replace $z_e$ by $z(e)$. 
503  14  Replace $O(E(H))$ by $O(\log E(H))$. 
511  30,32  Replace \delta_H by \delta_G in line 30 and \delta_H(X) by \delta_G(Y) in line 32. 
519  4  The paper by Kawarabayashi, Kobayashi and Reed [2010] appeared in the Journal of Combinatorial Theory B 102 (2012), 424435. 
523  3738,40  The definition of $q(U\cup\{x\},x)$ is not good, as Lemma 20.4(a) may not hold in general. To fix this, one can either require (w.l.o.g.) $c$ to be a metric or, easier, redefine $q$ as follows: $q(U\cup\{x\},x) := \min \{ c(E(S'))+c(E(S'')) : \emptyset \not= U'\subset U, S' is a Steiner tree for U'\cup\{x\} in G, S'' is a Steiner tree for (U\setminus U')\cup\{x\} in G \}$. Then (a) is trivial, and the proof of (b) is essentially unchanged. 
526  3032  The Steiner tree inapproximability bound was improved to 1.01 by Chlebík and Chlebíková [2008]. Reference: Chlebík, M., and Chlebíková, J.: The Steiner tree problem on graphs: Inapproximability results. Theoretical Computer Science 406 (2008), 207214 
529  1520  The proof of the first statement is not entirely clear, but it actually shows the stronger statement that there exists a spanning tree $M$ in $G[S]$ with $\sum_{\{s,t\}\in E(M)} dist_{(Y,c')}(s,t) \le c(E(Y))c(L)$. 
549  3031  Replace ≤ by ≥ and one δ_{G}(A) by δ_{G}(B) in both lines. 
553  2  Replace 0 by ∅. 
554  1921  The paper by Byrka et al. [2010] appeared in the Journal of the ACM 60 (2013), Article 6, with the title: Steiner tree approximation via iterative randomized rounding. 
556  6  The correct title of Kou's [1990] paper is "On efficient implementation of an approximation algorithm for the Steiner tree problem". 
562  67  The TSP inapproximability bound was improved to 123/122 by Karpinski, Lampis and Schmied [2013]. Reference: Karpinski, M., Lampis, M., Schmied, R. [2013]: New inapproximability bounds for TSP. Algorithms and Computation; Proceedings of ISAAC 2013; LNCS 8283 (L. Cai, S.W. Chen, T.W. Lam, eds.), Springer, Berlin 2013, pp. 568578 
590  2225  The paper by Asadpour et al. [2010] appeared in Operations Research 65 (2017), 10431061. Svensson, Tarnawski and Végh found a constantfactor approximation algorithm (arXiv:1708.04215). 
591  57  The paper by Englert, Röglin and Vöcking [2007] appeared in Algorithmica 68 (2014), 190264. 
591  1314  The paper by Fiorini et al. [2011] appeared in the Journal of the ACM 62 (2015), Article 17, entitled "Exponential lower bounds for polytopes in combinatorial optimization". 
617  7  "element of" should be "subset of". 
627  4246  The paper by Levi, Shmoys and Swamy [2004] appeared in Mathematical Programming A 131 (2012), 365379. 
627  4750  The paper by Li [2011] appeared in Information and Computation 222 (2013), 4558. 
Last change: September 5, 2017. Thanks to Maxim Babenko, Steffen Böhmer, Ulrich Brenner, György Dósa, Michael Etscheid, Jean Fonlupt, Stephan Held, Stefan Hougardy, Solomon Lo, Jens Maßberg, Dieter Rautenbach, Jan Schneider, Sophie Spirkl, and Uri Zwick.