In this chapter we present approximation algorithms for the metric Steiner tree problem and the metric traveling salesman problem. The reasons for considering the metric variants of these problems differ. For the Steiner tree problem, the metric case is the core of the general problem, and the general problem can be reduced to the metric one. For the traveling salesman problem, without this restriction no βgoodβ approximation algorithms exist, assuming \(P \neq N P\). Nevertheless, the approximation algorithms for these problems share a common idea, which we develop in this chapter.
The shortest common superstring problem (chapter βShortest common superstringβ in the βMiscellaneous topicsβ part) can also be reduced to the traveling salesman problem with a special metric, and a 4-approximation algorithm exists for it.
1 The metric Steiner tree problem
The Steiner tree problem was posed by Gauss in a letter to Schumacher. Given \(n\) cities in the plane, we must connect them by polygonal lines so that every city is connected to every other and the total length of all the lines drawn is minimized. Note that the optimal solution may include intermediate (Steiner) points, and all connections must be segments joining points (original or intermediate). We next consider the Steiner problem on graphs.
The Steiner tree problem
A graph \(G=(V, E)\), edge costs \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\), a subset \(R \subseteq V\).
A tree \(T\) of minimum cost such that \(R \subseteq T\), i.e., \(T\) contains all vertices of \(R\).
The set \(R\) is called the set of terminals. The set \(V \backslash R\) is called the Steiner set.
Special cases of the Steiner tree problem:
\(R = V\). In this case the Steiner tree problem is the minimum spanning tree (MST) problem;
\(R = \left\{ v_1, v_2\right\}\). In this case the Steiner tree problem is the problem of finding a minimum-weight path from \(v_1\) to \(v_2\).
The metric Steiner tree problem
A complete graph \(G=(V, E)\);
edge costs \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\) such that for any three vertices \(u, v\) and \(w\) the inequality \(\operatorname {cost}(u, v) \leq \operatorname {cost}(u, w)+\operatorname {cost}(w, v)\) holds;
a subset \(R \subseteq V\).
A tree \(T\) of minimum cost such that \(R \subseteq T\), i.e., \(T\) contains all vertices of \(R\).
The MST on the terminals is worse than the Steiner tree
The purple vertices \(v_1,v_2,v_3\) are terminals; the orange \(v_4\) is a Steiner vertex. The MST on the terminals alone (without \(v_4\)) is a feasible but not always optimal solution to the Steiner tree problem. Hover over an edge to see its cost.
Theorem 1 The existence of a \(\rho\)-approximation algorithm for the metric Steiner tree problem implies the existence of a \(\rho\)-approximation algorithm for the Steiner tree problem.
Mn-proofProof
Let \(I\) be an instance of the Steiner tree problem with graph \(G=\)\((V, E)\). From the graph \(G\) construct a complete graph \(G^{\prime }\) for an instance \(I^{\prime }\) of the metric Steiner tree problem. Define the cost of the edge \((u, v)\) in \(G^{\prime }\) as the cost of a shortest \(u\)β\(v\) path in \(G\). The graph \(G^{\prime }\) is called the metric closure of the graph \(G\). The set of terminals and the Steiner set are the same in both instances.
The cost of any edge \((u, v) \in E\) in the graph \(G^{\prime }\) does not exceed the cost of that edge in the graph \(G\). Hence the cost of an optimal solution of instance \(I\) does not exceed the cost of an optimal solution of instance \(I^{\prime }\).
Suppose we are given a Steiner tree \(T^{\prime }\) for instance \(I^{\prime }\). We show how to construct, in polynomial time, a Steiner tree of no greater cost for instance \(I\). The cost of the edge \((u, v)\) in the graph \(G^{\prime }\) corresponds to the cost of a path in the graph \(G\). Replace each edge of the tree \(T^{\prime }\) by the corresponding path to obtain a subgraph of \(G\). Clearly, in this subgraph all vertices of the terminal set are connected. However, this subgraph may in general contain a cycle. If so, remove redundant edges to obtain a tree \(T\).
Let \(C^{\prime }\) be a solution found by a \(\rho\)-approximation algorithm for the metric Steiner tree problem. Using the method described above, find a solution of cost \(C\) for the Steiner tree problem such that
A minimum spanning tree is not always an optimal solution of the Steiner tree problem. However, the cost of a minimum spanning tree is a good bound on the cost of an optimal Steiner tree.
Theorem 2 Let \(R \subseteq V\) be the set of terminals in the Steiner tree problem. Then the cost of a minimum spanning tree on \(R\) does not exceed twice the cost of an optimal Steiner tree in the graph \(G\).
Proof of the factor-2 bound for the Steiner tree problem
Purple vertices are terminals, orange are Steiner vertices. The button traces the tour: on the left, an Eulerian tour of the doubled Steiner tree (cost \(2\cdot\mathrm{OPT}\)); on the right, the same tour "shortcut," skipping the Steiner vertices and repeat visits.
βΆ
(a) We double the edges of the Steiner tree β this gives an Eulerian graph of cost \(2\cdot\mathrm{OPT}\). (b) We "shortcut," skipping the Steiner vertices and repeat visits β this gives a Hamiltonian cycle on the terminals; by the triangle inequality its cost is \(\le 2\cdot\mathrm{OPT}\), and the MST on \(R\) is no more expensive than this cycle: \(\mathrm{cost}(\mathrm{MST}(R))\le 2\cdot\mathrm{OPT}\).
Algorithm 1Spanning Tree algorithm (\(G=(V, E), R, \operatorname {cost}: E \to \mathbb {Q}_+\))
Find a minimum spanning tree \(T\) on the vertex set \(R\).
return\(T\).
A tight example for the 2-approximation of the Steiner tree problem
\(n\) terminals on a circle and one Steiner vertex at the center. Edges to the center cost \(1\), edges between neighboring terminals cost \(2\). The MST on the terminals (a cycle minus one edge) costs \(2(n-1)\), the Steiner tree (a star) costs \(n\); the ratio \(\to2\).
6
Can we do better? Yes! The best known algorithm achieves \(\rho = \ln (4) + \varepsilon \approx 1.39\).
It is also known that no algorithm can achieve \(\rho < \frac{96}{95} \approx 1.0105\) (assuming \(\operatorname {P} \neq \operatorname {NP}\)).
2 The metric traveling salesman problem
2.1 The general traveling salesman problem is inapproximable
The traveling salesman problem is one of the best-known problems in combinatorial optimization: find the cheapest route that visits each of the given cities exactly once and then returns to the starting city.
The traveling salesman problem
A complete graph \(G=(V, E)\), edge costs \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\).
A Hamiltonian cycle \(C\) of minimum cost.
A cycle that contains all vertices is called Hamiltonian.
Theorem 3 For any polynomially computable function \(\alpha (n)\), there is no \(\rho\)-approximation algorithm with \(\rho =\alpha (n)\) for the traveling salesman problem, unless \(P = N P\).
Mn-proofProof
We argue by contradiction. Suppose a \(\rho\)-approximation algorithm \(\mathcal{A}\) with \(\rho =\alpha (n)\) exists for the traveling salesman problem. We show that the polynomial-time algorithm \(\mathcal{A}\) could then be used to solve the NP-hard Hamiltonian cycle problem. This would imply \(P=N P\).
The basic idea of the reduction is to construct, from the graph \(G\), a complete weighted graph \(G^{\prime }\) such that:
if \(G\) has a Hamiltonian cycle, then the cost of an optimal solution of the traveling salesman problem on \(G^{\prime }\) equals \(n\), and
if \(G\) has no Hamiltonian cycle, then the optimal solution of the traveling salesman problem for \(G^{\prime }\) has cost greater than \(\alpha (n) \cdot n\).
Note that on the graph \(G^{\prime }\) the algorithm \(\mathcal{A}\) must find a solution of cost \(\operatorname {cost} \leq \alpha (n) \cdot n\) in the first case and of cost \(\operatorname {cost} > \alpha (n) \cdot n\) in the second case.
From the graph \(G\) construct a complete weighted graph \(G^{\prime }\). Assign cost 1 to the edges present in \(G\), and cost \(\alpha (n) \cdot n\) to the edges absent from \(G\). If \(G\) has a Hamiltonian cycle, then the corresponding tour in \(G^{\prime }\) has cost \(n\). On the other hand, if \(G\) has no Hamiltonian cycle, then any tour in \(G^{\prime }\) must use an edge of cost \(\alpha (n) \cdot n\), so the cost of the tour will be \(\operatorname{cost} >\alpha (n) \cdot n\).
Note that this proof of strong inapproximability uses edge costs that violate the triangle inequality. If we restrict attention to graphs on which this inequality holds, i.e., to the metric traveling salesman problem, the problem remains NP-hard but is no longer as hard to approximate.
The metric traveling salesman problem
A complete graph \(G=(V, E)\), edge costs \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\) such that for any three vertices \(u, v\) and \(w\)\[
\operatorname {cost}(u, v) \leq \operatorname {cost}(u, w)+\operatorname {cost}(w, v)
\]
A Hamiltonian cycle \(C\) of minimum cost.
2.2 A \(2\)-approximation algorithm
We present a simple 2-approximation algorithm for the metric traveling salesman problem. As a lower bound we use the optimal solution of the minimum spanning tree problem on the graph \(G\). This solution is a lower bound for the optimal solution of the traveling salesman problem, since removing any edge from a Hamiltonian cycle yields a spanning tree of \(G\).
Algorithm 2Double Spanning Tree algorithm (\(G=(V, E), \operatorname {cost} : E \rightarrow \mathbf{Q}^{+}\))
Find a minimum spanning tree \(T\) in the graph \(G\).
Double every edge of the tree \(T\) to obtain an Eulerian graph \(H\).
Find an Eulerian tour \(R\) in the graph \(H\).
Build a Hamiltonian cycle \(C\) by visiting the vertices of \(G\) in the order in which they occur in \(R\).
return\(C\).
Note that step 4 amounts to the shortcutting technique used in the theorem above.
The "double tree" algorithm for the metric traveling salesman problem
1) build an MST; 2) double its edges β this gives an Eulerian graph β and traverse it; 3) "shortcut," skipping already-visited vertices, to get a Hamiltonian cycle of cost \(\le 2\cdot\mathrm{MST}\le 2\cdot\mathrm{OPT}\). On steps 3 and 4 the tour is animated as it is traced.
Theorem 4 The Double Spanning Tree algorithm is a \(2\)-approximation algorithm for the metric traveling salesman problem.
Mn-proofProof
As noted above, \(\operatorname {cost}(T) \leq \operatorname {OPT}\). Since the graph \(H\) contains every edge of the tree \(T\) twice, \(\operatorname {cost}(R)=2 \cdot \operatorname {cost}(T)\). Then by the triangle inequality, after shortcutting we get \(\operatorname {cost}(C) \leq \operatorname {cost}(R)\) and \(\operatorname {cost}(C) \leq 2 \cdot \operatorname {OPT}\).
Tightness of the factor-2 bound for the "double tree" algorithm
A complete graph on \(n\) vertices (here \(n=6\)) with edges of cost \(1\) and \(2\): the bold cost-\(1\) edges form a star \(K_{1,n-1}\) and a cycle on the remaining \(n-1\) vertices. Hover over an edge to see its cost; the button on the right traces a bad tour.
(a) The optimal traveling-salesman tour, of cost \(n=6\): a cycle along the cheap edges (center \(\to\) outer vertex \(\to\) around the cycle \(\to\) center). (b) If the algorithm finds an MST shaped like a star, and the Eulerian tour visits the vertices in the order \(5,3,2,1,4,6\), then after shortcutting the cycle contains \(n-2\) edges of cost \(2\) β cost \(2n-2\), twice the optimum as \(n\to\infty\).
2.3 A \(1.5\)-approximation algorithm
The Double Spanning Tree algorithm first finds a cheap Eulerian tour from a spanning tree of the graph \(G\), and then turns it into a traveling-salesman tour by shortcutting. Is there an Eulerian tour other than the one found via the double spanning tree? Recall that a graph has an Eulerian tour if and only if every vertex has even degree. Let \(V^{\prime }\) be the set of all vertices of odd degree in the spanning tree. Then the number of such vertices \(\left|V^{\prime }\right|\) must be even, since the sum of the degrees of all vertices in any graph is even. If we add to the minimum spanning tree a minimum-weight perfect matching on the set \(V^{\prime }\), then every vertex will have even degree, and we obtain an Eulerian graph. Recall that the minimum-cost perfect matching problem can be solved in polynomial time.
Find a minimum spanning tree \(T\) in the graph \(G\).
Find a minimum-cost matching \(M\) on the set of vertices of \(T\) having odd degree.
Add the edges of \(M\) to \(T\) to obtain an Eulerian graph \(H\).
Find an Eulerian tour \(R\) in the graph \(H\).
Build a Hamiltonian cycle \(C\) by visiting the vertices of \(G\) in the order in which they occur in \(R\).
return\(C\).
The Christofides-Serdyukov algorithm
The same graph \(v_1,\ldots,v_9\) as in the "double tree" algorithm. Instead of doubling the whole tree, we add only a minimum perfect matching on the odd-degree vertices β the tour is cheaper: \(\le\frac32\cdot\mathrm{OPT}\). Hover over a vertex to see its degree.
To bound the accuracy of this algorithm, we present a new lower bound on the cost of an optimal solution of the traveling salesman problem.
Lemma 1 Let \(V^{\prime } \subseteq V\) with \(\left|V^{\prime }\right|\) even, and let \(M\) be a minimum-cost perfect matching for \(V^{\prime }\). Then \(\operatorname {cost}(M) \leq \operatorname {OPT} / 2\).
Mn-proofProof
Consider an optimal cycle \(\tau\) for the traveling salesman problem on the graph \(G\). Let the cycle \(\tau^{\prime }\) be obtained from \(\tau\) on the vertex set \(V^{\prime }\) by shortcutting. By the triangle inequality, \(\operatorname {cost}\left(\tau^{\prime }\right) \leq \operatorname {cost}(\tau )\). But \(\tau^{\prime }\) is the union of two perfect matchings on \(V^{\prime }\), formed from the alternating edges of the cycle \(\tau^{\prime }\). Hence the smaller of the two matchings has cost at most \(\operatorname {cost}\left(\tau^{\prime }\right) / 2 \leq \operatorname {OPT} / 2\). Consequently, the optimal matching also has cost at most \(\operatorname {OPT} / 2\).
Theorem 5 The ChristofidesβSerdyukov algorithm is a \(\frac{3}{2}\)-approximation algorithm for the metric traveling salesman problem.
Mn-proofProof
We bound the cost of the Eulerian tour \(R\): \[
\operatorname {cost}(R) \leq \operatorname {cost}(T)+\operatorname {cost}(M) \leq \operatorname {OPT}+\frac{1}{2} \operatorname {OPT}=\frac{3}{2} \operatorname {OPT}
\] Using the triangle inequality, we get \(\operatorname {cost}(C) \leq \operatorname {cost}(R)\). This proves the theorem.
Tightness of the \(3/2\) bound for the Christofides-Serdyukov algorithm
A zigzag chain of \(m=\lceil n/2\rceil\) triangles, all edges shown have cost \(1\). The bold edges are the MST \(T\) (a zigzag path): it has exactly two odd-degree vertices β the endpoints β and the matching on them is a single edge between the endpoints, whose cost (under the shortest-path metric) equals \(\lceil n/2\rceil\). The button traces the algorithm's tour.
4
Can one find an algorithm with better accuracy? Yes! In 2020 an algorithm with accuracy \(\alpha < 1.5 - 10^{-36}\) was obtained. As one can see, the improvement is not very substantial. The search for better approximation algorithms with guaranteed accuracy bounds for the metric traveling salesman problem continues. Many researchers believe that a \(\frac{4}{3}\)-approximation algorithm ought to exist.
The metric traveling salesman problem cannot be approximated within a factor smaller than \(\frac{123}{122} \approx 1.008\) (assuming \(\operatorname {P} \neq \operatorname {NP}\)).
For the Euclidean traveling salesman problem (the case where the vertices of the graph are points in \(\mathbb {R}^{n}\) and the edge cost equals the Euclidean distance), there exists an approximation algorithm with factor \((1+\varepsilon )\) for every \(\varepsilon > 0\), i.e., a polynomial-time approximation scheme exists. However, it is not fully polynomial: the dependence on \(\frac{1}{\varepsilon }\) is not polynomial.
3 Exercises
ProblemProblem 1
The difficulty of the Steiner tree problem lies in finding the optimal subset of Steiner vertices to include in the tree. Show that if this set is known, the Steiner tree problem can be solved in polynomial time.
ProblemProblem 2
Find an approximate solution of the traveling salesman problem for the complete graph in the figure below, using the Double Spanning Tree algorithm and the ChristofidesβSerdyukov algorithm.
Traveling salesman problem: a problem instance
A complete graph on 7 vertices \(A,\ldots,G\); the edges \((A,E)\), \((B,F)\), \((C,G)\) all cost \(19\). Hover over a vertex to highlight all its edges, or over the midpoint of an edge to see its cost. Find approximate solutions to the traveling salesman problem.
ProblemProblem 3
Consider the variant of the metric traveling salesman problem in which we must find a simple path containing all vertices of the graph. Depending on the number of specified path endpoints (0, 1, or 2), three problems arise.
Construct a \(3/2\)-approximation algorithm for the case where only one endpoint, or none, is specified.
Construct a \(5/3\)-approximation algorithm for the case where both endpoints are specified.
ProblemProblem 4
Consider the following algorithm for the metric traveling salesman problem. First find the two closest cities, denote them \(i\) and \(j\). Build a cycle \(S\) through them: \(i \rightarrow j \rightarrow i\). At each subsequent iteration, find a pair of cities \(i \in S\) and \(j \notin S\) with minimum distance \(c_{i j}\). Insert the city \(j\) into the cycle \(S\) immediately after the city \(i\). Prove that this algorithm is a \(2\)-approximation algorithm.