In this introductory chapter, we will formally introduce the main variants of the traveling salesman problem, symmetric and asymmetric, explain a very useful graph-theoretic view based on Euler’s theorem, and describe the classical simple approximation algorithms: Christofides’ algorithm and the cycle cover algorithm.

We also introduce basic notation, in particular from graph theory, and some fundamental combinatorial optimization problems.

A major step towards the first constant-factor approximation algorithm for the Asymmetric TSP was made by Svensson. He devised a constant-factor approximation algorithm for Asymmetric Graph TSP, which is the special case of the Asymmetric TSP with c(e)=1 for all e ∈ E.

In this chapter, we present Svensson’s algorithm for the Asymmetric Graph TSP. We also incorporate some improvements, from Traub and Vygen, who gave a variant of Svensson’s algorithm with improved approximation ratio. Moreover, we present an improved algorithm for finding a graph subtour cover, which is the main subroutine of Svensson’s algorithm. Overall, we will obtain an approximation ratio of 8+ε for Asymmetric Graph TSP, for every ε>0.

Almost all techniques presented in this chapter will be used again in Chapters 7 and 8 for the general Asymmetric TSP.

The random sampling approach described in Chapter 5 for the Asymmetric TSP has also been used successfully for the Symmetric TSP. First, Oveis Gharan, Saberi, and Singh obtained the first algorithm with approximation ratio less than 3/2 for Graph TSP. More recently, Karlin, Klein, and Oveis Gharan proved that essentially the same algorithm has approximation ratio less than 3/2 for the general Symmetric TSP.

The algorithm is simple, but its analysis is very complicated. While for Graph TSP we know simpler and better algorithms today (see Chapters 12 and 13), the random sampling algorithm is still the best-known approximation algorithm for Symmetric TSP.

The algorithm samples a spanning tree from an (approximately) marginal-preserving λ-uniform distribution and then proceeds with parity correction like Christofides’ algorithm. After briefly discussing the analysis for Graph TSP, we present the first part of the analysis by Karlin, Klein, and Oveis Gharan, with some simplifications suggested by Drees. The main point is to reduce the set of relevant cuts that need to be considered to bound the cost of parity correction and obtain a nice structure that will be exploited in Chapter 11.

Traub and Vygen used recursive dynamic programming to obtain a (3/2+ε)-approximation algorithm for Path TSP for any ε>0. This approach was then improved and simplified by Zenklusen, who obtained a 3/2-approximation for Path TSP. After discussing the dynamic programming approach in a simple context, we present Zenklusen’s algorithm.

Then we present a black-box reduction from Path TSP to Symmetric TSP, similar to the one proposed by Traub, Vygen, and Zenklusen. This shows that the former is not much harder to approximate than the latter. This implies the currently best-known approximation guarantees for Path TSP and the special case Graph Path TSP. Our new proof, again based on dynamic programming, actually yields the same result even for a more general problem, which we call Multi-Path TSP.

So far, all algorithms for Symmetric TSP began with a spanning tree and then added edges to make the graph Eulerian. In contrast, Mömke and Svensson suggested to begin with a 2-connected graph; then we may also delete some edges for making it Eulerian, and this may be cheaper overall. They introduced the notion of removable pairings, which allow to control that we maintain connectivity when deleting edges.

This idea led to a substantial improvement and is still used for the best algorithm for Graph TSP that we know today (cf. Chapter 12). It also yields the ratio 4/3 for the special case of subcubic graphs.

In this short concluding chapter, we show two figures that summarize the state of the art.

Moreover, we list again the open problems that we mentioned in this book.

In this chapter, we mention further results on the approximability of variants or special cases of the traveling salesman problem. We will also briefly mention a few important related problems for which the best-known approximation algorithms use a TSP approximation algorithm as a subroutine.

In particular, we discuss inapproximability results, geometric special cases, the minimum 2-edge-connected spanning subgraph problem, the prize-collecting TSP, the a priori TSP, and capacitated vehicle routing.

A natural generalization of the (asymmetric) traveling salesman problem arises when we are given a start vertex s and an end vertex t and ask for a tour that begins in s and ends in t, rather than a round trip.

While this problem seems to be harder, we will see in this chapter that it can be tackled by similar techniques. In particular, we show black-box reductions (by Feige and Singh, and by Köhne, Traub, and Vygen) to Asymmetric TSP and prove, as new results, the best-known approximation ratios and bounds on the integrality ratio of the natural LP relaxation.

Like in the asymmetric case (cf. Chapter 9), one can consider the generalization of Symmetric TSP where the start and end of the tour that we are looking for are not necessarily identical. Christofides’ algorithm can be generalized to this problem but only yields a 5/3-approximation here.

This chapter contains basic results about this problem and also a further generalization called T-tours; these results will be used in subsequent chapters where we will present better approximation algorithms. One important observation is that the "narrow cuts" of an LP solution have a nice structure.

For unweighted graphs, a 3/2-approximation algorithm can be obtained with the techniques of Chapter 13, or with a simple LP-based approach that we will present in this chapter.

As in the symmetric case, there are two versions of the Asymmetric TSP and two corresponding LP relaxations. They are related to circulations in digraphs. Using again the splitting-off technique, we show that the two versions are equivalent, and we will present a third equivalent version.

We will also study the integrality ratio of the Asymmetric TSP LPs and show that it is at least 2, even for unweighted graph instances.

For NP-hard problems, it is often useful to study relaxations that are easier to solve. In the previous chapter, we already saw two approximation algorithms that started by solving a relaxation: finding a minimum-cost connected spanning subgraph in Christofides’ algorithm and finding a minimum-cost cycle cover in the cycle cover algorithm.

Another kind of relaxation arises by formulating the problem as an integer linear program and dropping the integrality constraints. In this chapter, we will study such linear programming relaxations for Symmetric TSP with Triangle Inequality and Symmetric TSP. These two equivalent versions of the problem give rise to two linear programming relaxations, which turn out to be equivalent as well (by the splitting-off technique). We also study polyhedral descriptions of connectors and T-joins and the integrality ratio of the subtour LP.

In this chapter, we will present an algorithm for the subtour cover problem, which we defined in Chapter 7. This will complete the constant-factor approximation algorithm for the Asymmetric TSP.

The subtour cover problem was introduced (in a slightly different form) by Svensson, Tarnawski, and Végh, who gave a (4,2,1)-algorithm for subtour cover. Traub and Vygen strengthened this to a (3,2,1)-algorithm. Here, we further improve this to a (2,2,1)-algorithm. Our subtour cover algorithm builds on the algorithm for the graph subtour cover problem that we presented in Section 6.2.

As a final result, we obtain a (17+ε)-approximation for the Asymmetric TSP for any fixed ε>0.

While many exact and approximation algorithms work with a linear programming formulation (often a relaxation), the dual LP often plays a key role in the algorithms and their analysis. In this chapter, we analyze the structure of optimum dual solutions for the classical LP relaxations of the TSP, but also for T-joins, and deduce properties like laminarity.

By an efficient uncrossing algorithm and by analyzing extreme point solutions, we obtain optimum primal and dual solutions with linear-size support. Since the primal constraints and dual variables correspond to cuts, enumerating all cuts with a small value is a useful tool in several algorithms.

An, Kleinberg, and Shmoys were the first to beat Christofides’ algorithm for Path TSP. Their algorithm, which they called Best-of-Many Christofides, is very natural: Since an LP solution can be written as convex combination of spanning trees, we can do parity correction on each of these trees and output the best of the resulting tours. It turns out that this yields a better guarantee than the 5/3 that Christofides’ algorithm yields.

In this chapter, we analyze this algorithm and study various follow-up works that have yielded better and better approximation ratios; some of them also apply to general T-tours. This includes a structured decomposition into spanning trees (by Gottschalk and Vygen), Best-of-Many Christofides with lonely edge deletion (by Sebő and van Zuylen), and Traub’s T-tour algorithm.

After the O(log n)-approximation algorithms for Asymmetric TSP, the first algorithm to beat the cycle cover algorithm by more than a constant factor was found in 2009 by Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi. Their approach is based on finding a "thin" (oriented) spanning tree and then adding edges to obtain a tour. A major open question is how thin trees are guaranteed to exist.

The O(log n/loglog n)-approximation algorithm by Asadpour et al. samples a random spanning tree from the maximum entropy distribution. To show how this works, we discuss interesting connections between random spanning trees and electrical networks. Some results of this chapter will be used again in Chapters 10 and 11.