Approximation Algorithms for Traveling Salesman Problems

Errata

• p.28: In Theorem 2.10, the vectors $c$ and $a$ should be from $\mathbb{Q}^{d(n)}$ and do not need to be nonnegative.
• p.75: In the second row of the inequality chain, one $\cap$ should be $\cup$.
• p.270,272: In the proof of Theorem 12.6 and throughout Section 12.4 we may assume that $G$ is 2-vertex-connected (by Proposition 12.1). In Algorithm 12.9, after Step (1), we should assume that the support graph of $x$ is 2-vertex-connected and consider the blocks separately otherwise.
• p.274: The definition of $cost_v(f)$ for $v=r$ should not contain the second term (the sum).
• p.290: In the proof of Theorem 13.11, first reorder the ears $P_2,...,P_k$ so that we obtain an ear-decomposition for which $(i,-j)$ is lexicographically maximum; only then we can guarantee that $P_{new}$ is open.
• p.403: In the comment after Open Problem 1.33, $10^{36}$ should be $10^{-36}$.
• p.404: In the comment after Open Problem 12.12, $\frac{11}{9}$ should be $\frac{13}{9}$.