Combinatorial Optimization

Theory and Algorithms

Algorithms and Combinatorics 21
Springer-Verlag, Berlin Heidelberg New York Tokyo Paris Milano

First Edition 2000
Second Edition 2002
Japanese Edition 2005
Third Edition 2006
Fourth Edition 2008
German Edition 2008
Second Japanese Edition 2009
French Edition 2010
Italian Edition 2011
Fifth Edition 2012
Second German Edition 2012
Chinese Edition forthcoming
Russian Edition forthcoming

Preface and Table of Contents (5th edition)

More Information from the publishers:

List of Updates and Errors of the Fifth Edition

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$.

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), to appear

206 40 The correct page numbers of the paper by Cheung, Lau and Leung [2011] are 197-206.

245 27 The coordinates should be independent.

267 1 Replace k by n.

362 30 The proof should begin with the following: Without loss of generality, $f(\emptyset) = g(\emptyset)$ and $f(E) = g(E)$.

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.

503 14 Replace $O(|E(H)|)$ by $O(\log |E(H)|)$.

519 4 The paper by Kawarabayashi, Kobayashi and Reed [2010] appeared in the Journal of Combinatorial Theory B 102 (2012), 424-435.

526 30-32 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), 207-214

554 19-21 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.

562 6-7 The TSP inapproximability bound was improved to 185/184 by Lampis [2012]. Reference: Lampis, M. [2012]: Improved inapproximability for TSP. Approximation, Randomization, and Combinatorial Optimization; Proceedings of the 16th APPROX Workshop 2012; LNCS 7408 (A. Gupta, K. Jansen, J. Rolim, R. Servedio, eds.), Springer, Berlin 2012, pp. 243-253

591 13-14 The paper by Fiorini et al. [2011] appeared in the Proceedings of the 44th Annual ACM Symposium on Theory of Computing (2012), 95-106.

617 7 "element of" should be "subset of".

627 47-50 The paper by Li [2011] appeared in Information and Computation 222 (2013), 45-58.

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$.
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), to appear
206	40	The correct page numbers of the paper by Cheung, Lau and Leung [2011] are 197-206.
245	27	The coordinates should be independent.
267	1	Replace k by n.
362	30	The proof should begin with the following: Without loss of generality, $f(\emptyset) = g(\emptyset)$ and $f(E) = g(E)$.
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.
503	14	Replace $O(\|E(H)\|)$ by $O(\log \|E(H)\|)$.
519	4	The paper by Kawarabayashi, Kobayashi and Reed [2010] appeared in the Journal of Combinatorial Theory B 102 (2012), 424-435.
526	30-32	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), 207-214
554	19-21	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.
562	6-7	The TSP inapproximability bound was improved to 185/184 by Lampis [2012]. Reference: Lampis, M. [2012]: Improved inapproximability for TSP. Approximation, Randomization, and Combinatorial Optimization; Proceedings of the 16th APPROX Workshop 2012; LNCS 7408 (A. Gupta, K. Jansen, J. Rolim, R. Servedio, eds.), Springer, Berlin 2012, pp. 243-253
591	13-14	The paper by Fiorini et al. [2011] appeared in the Proceedings of the 44th Annual ACM Symposium on Theory of Computing (2012), 95-106.
617	7	"element of" should be "subset of".
627	47-50	The paper by Li [2011] appeared in Information and Computation 222 (2013), 45-58.

Last change: October 30, 2013. Thanks to Ulrich Brenner, Stephan Held, Stefan Hougardy, Jens Maßberg, and Jan Schneider.

Bernhard Korte Jens Vygen