35.2 The traveling-salesman problem

35.2-1

Suppose that a complete undirected graph $G = (V, E)$ with at least $3$ vertices has a cost function $c$ that satisfies the triangle inequality. Prove that $c(u, v) \ge 0$ for all $u, v \in V$.

Let $u, v \in V$. Let $w$ be any other vertex in $V$. Then by the triangle inequality we have

$$ \begin{aligned} c(w, u) + c(u, v) &\ge c(w, v) \\ c(w, v) + c(v, u) &\ge c(w, u). \end{aligned} $$

Adding the above inequalities together gives

$$ \cancel{c(w, u)} + \cancel{c(w, v)} + c(u, v) + c(v, u) \ge \cancel{c(w, v)} + \cancel{c(w, u)}. $$

Since $G$ is undirected we have $c(u, v) = c(v, u)$, and so the above inequality gives $2c(u, v) \ge 0$ from which the result follows.

35.2-2

Show how in polynomial time we can transform one instance of the traveling-salesman problem into another instance whose cost function satisfies the triangle inequality. The two instances must have the same set of optimal tours. Explain why such a polynomial-time transformation does not contradict Theorem 35.3, assuming that $\text P \ne \text{NP}$.

(Omit!)

35.2-3

Consider the following closest-point heuristic for building an approximate traveling-salesman tour whose cost function satisfies the triangle inequality. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex $u$ that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest $u$ is vertex $v$. Extend the cycle to include $u$ by inserting $u$ just after $v$. Repeat until all vertices are on the cycle. Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.

(Omit!)

35.2-4

In the bottleneck traveling-salesman problem, we wish to find the hamiltonian cycle that minimizes the cost of the most costly edge in the cycle. Assuming that the cost function satisfies the triangle inequality, show that there exists a polynomial-time approximation algorithm with approximation ratio $3$ for this problem. ($\textit{Hint:}$ Show recursively that we can visit all the nodes in a bottleneck spanning tree, as discussed in Problem 23-3, exactly once by taking a full walk of the tree and skipping nodes, but without skipping more than two consecutive intermediate nodes. Show that the costliest edge in a bottleneck spanning tree has a cost that is at most the cost of the costliest edge in a bottleneck hamiltonian cycle.)

(Omit!)

35.2-5

Suppose that the vertices for an instance of the traveling-salesman problem are points in the plane and that the cost $c(u, v)$ is the euclidean distance between points $u$ and $v$. Show that an optimal tour never crosses itself.

(Omit!)