In the metric asymmetric traveling salesman problem, we are given as input a complete directed graph with costs for all arcs , such that the arc costs obey the triangle inequality: for all , we have that . 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 there is a path from to and a path from to . 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.
- Prove that the subgraph found by the algorithm is a strongly connected Eulerian subgraph of the input graph.
- Prove that the cost of this subgraph is at most OPT, where and OPT is the cost of the optimal tour. Conclude that this algorithm is a -approximation algorithm for the metric asymmetric traveling salesman problem.