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?

Improve this question
$\endgroup$
4
  • $\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, 2014 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, 2014 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, 2014 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, 2014 at 17:19

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.