3
$\begingroup$

Is it possible to implement the Christofides algorithm for an directed Graph?

Suppose you have an undirected Graph, in which every vertex has an edges in both ways to every other in the graph (not to itself). But the weights of the edges, don't necessarily have do be the same in both ways (unsymmetrical).

For Example you think of a Street Map, in which there are a lot of oneway streets.

We now want to find an approximation for the traveling salesman tour through all the vertices.

First of all the Christoffides algorithm is not defined for such an TSP, because the Minimum Spanning Tree ist not defined for an directed Graph.

But still we start the algorithm by finding the optimum branching with Edmonds algorithm to the start point of the tour as the root.

Then we find a minimal perfect matching for the branching, so that it becomes an Eulerian graph. This will happen with the Hungarian algorithm, wich finds an minimal matching so that every vertex in the branching has afterwords the same amount of edges coming in an out.

In the last step we find the euler tour and optimize the tour by taking shortcuts.

I have to questions:

Is the way I want to implement the algorithm right, or did I made a mistake and it can't work If it works, is it still bounded bei 1,5 of the optimal solution for the tsp?

$\endgroup$
  • $\begingroup$ I absolutely don't know the algorithm, but perhaps you can convert a directed graph to an undirected equivalent replacing every node with 3 adjacent nodes ($u_1\to u_2 \to u_3$) in which $u_1$ "receives" the incoming edges, $u_3$ "send" the outgoing edges. $\endgroup$ – Marzio De Biasi Jun 12 '14 at 8:02
  • 4
    $\begingroup$ The best known approximation ratio for asymmetric TSP is $O(\log n/\log \log n)$ cs.cmu.edu/~odonnell/hits09/…. In your question, I don't see how you make the branching Eulerian by adding a matching. The discrepancy between in- and outdegree for vertices can be arbitrarily bad in the branching. $\endgroup$ – Sasho Nikolov Jun 12 '14 at 9:32
  • $\begingroup$ As Sasho mentioned best algorithm for a metric atsp is by Asadpoor etal. But in directed case general idea is to use some good spanning tree and in their paper they called it thin tree. To overcome problem of different weights in different direction we should normalize weights to be almost same in both direction. E.g you can set edge weight be the average of two edges. This was just an example but even in real approximations we use similar simple ideas but proof is complicated(consequencely finding good tree to have approximable behavior is complicated). $\endgroup$ – Saeed Jun 19 '14 at 17:16
  • $\begingroup$ By the way if is not in a metric space we cannot expect any apx . and I cannot see any metric restriction in your question. $\endgroup$ – Saeed Jun 19 '14 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.