Traveling Salesman Problem/Triangle Inequality) Consider a symmetric traveling salesman problem where the arc costs are nonnegative and satisfy the following triangle inequality:
This problem has some special algorithmic properties.
(a) Consider a procedure, which given a cycle {i0, i1,...,iK, i0} that contains all the nodes (but passes through some of them multiple times), obtains a tour by deleting nodes after their first appearance in the cycle; e.g., in a 5-node problem, starting from the cycle {1, 3, 5, 2, 3, 4, 2, 1}, the procedure produces the tour {1, 3, 5, 2, 4, 1}. Use the triangle inequality to show that the tour thus obtained has no greater cost than the original cycle.
(b) Starting with a spanning tree of the graph, use the procedure of part (a) to construct a tour with cost equal to at most two times the total cost of the spanning tree. Hint: The cycle should cross each arc of the spanning tree exactly once in each direction. "Double" each arc of the spanning tree. Use the fact that if a graph is connected and each of its nodes has even degree, there is a cycle that contains all the arcs of the graph exactly once (cf. Exercise 1.5).
(c) (Double tree heuristic) Start with a minimum cost spanning tree of the graph, and use part (b) to construct a tour with cost equal to at most twice the optimal tour cost. (d) Verify that the problem of Fig. 10.18 satisfies the triangle inequality. Apply the method of part (c) to this problem
Exercise 1.5 Consider the problem of finding a shortest (forward) path from an origin node s to a destination node t of a graph with given arc lengths, subject to the additional constraint that the path passes through every node exactly once.
(a) Show that the problem can be converted to a traveling salesman problem by adding an artificial arc (t, s) of length -M, where M is a sufficiently large number.
(b) (Longest Path Problem) Consider the problem of finding a simple forward path from s to t that has a maximum number of arcs. Show that the problem can be converted to a traveling salesman problem.
