Question

asymmetric_tsp

In the metric asymmetric traveling salesman problem, we are given as input a complete directed graph G=(V,A)G = (V, A) with costs cij0c_{ij} \geq 0 for all arcs (i,j)A(i, j) \in A, such that the arc costs obey the triangle inequality: for all i,j,kVi,j,k \in V, we have that cij+cjkcikc_{ij} + c_{jk} \geq c_{ik}. The goal is to find a tour of minimum cost, that is, a directed cycle that contains each vertex exactly once, such that the sum of the cost of the arcs in the cycle is minimized.

One approach to finding an approximation algorithm for this problem is to first find a minimum-cost strongly connected Eulerian subgraph of the input graph. A directed graph is strongly connected if for any pair of vertices i,jVi,j \in V there is a path from ii to jj and a path from jj to ii. A directed graph is Eulerian if the indegree of each vertex equals its outdegree. Given a strongly connected Eulerian subgraph of the input to the problem, it is possible to use a technique called "shortcutting" to turn this into a tour of no greater cost by using the triangle inequality.

One way to find a strongly connected Eulerian subgraph is as follows: We first find a minimum mean-cost cycle in the graph. A minimum mean-cost cycle is a directed cycle that minimizes the ratio of the cost of the arcs in the cycle to the number of arcs in the cycle. Such a cycle can be found in polynomial time. We then choose one vertex of the cycle arbitrarily, remove all other vertices of the cycle from the graph, and repeat. We do this until only one vertex of the graph is left. Consider the subgraph consisting of all the arcs from all the cycles found.

  1. Prove that the subgraph found by the algorithm is a strongly connected Eulerian subgraph of the input graph.
  2. Prove that the cost of this subgraph is at most 2Hn2H_n \cdotOPT, where n=Vn = |V| and OPT is the cost of the optimal tour. Conclude that this algorithm is a 2Hn2H_n-approximation algorithm for the metric asymmetric traveling salesman problem.
1

Answers

1. We prove by induction on the size of the graph. Assume that the subgraph obtained from the (complete) graph after removing the vertices from the first cycle is indeed strongly connected Eulerian graph, now add back the removed vertices with the arcs of the cycle, clearly, the result graph is strongly connected Eulerian graph.

2. One can check that the number of arcs found in this process is it most 2n, this is because there are at most nn iterations and in each iteration the number of arcs that are found is the number of vertices we remove + 1. Now, in each iteration consider the optimal tour restricted to the vertices that have not been deleted yet, clearly the cost of such a tour is at most the value of OPT. This implies that in each iteration there is a cycle with mean-cost equals to OPTni\frac{OPT}{n_i} where nin_i is the number of vertices left in the beginning of the iith iteration. So the total cost of the arcs can be bound from above by 2i=1tOPTni2HnOPT2\sum_{i = 1}^t \frac{OPT}{n_i} \leq 2H_n \cdot OPT where tt is the number of iterations. To conclude that this algorithm is a 2Hn2H_n-approximation algorithm it is enough to see that a shortcut of the Eulerian tour costs less than the Eulerian tour itself.

1
Feedback