Hi Paolo,

Yes, the Christofides algorithm requires a minimum weight perfect matching, and unfortunately there's no simple reduction from the problem of finding a weighted matching to the problem of finding a maximum cardinality matching. I haven't used metric_tsp_approx before, but if you're just adding one node n to an already complete graph and connecting it to s and d, could you just add all of the other edges between n and other nodes in the graph and set those edge weights to "infinity" (something bigger than the sum of all of the edge weights in the graph) to force metric_tsp_approx to avoid those edges?

-Aaron


On Wed, Feb 12, 2014 at 6:06 AM, Paolo Bolzoni <paolo.bolzoni.brown@gmail.com> wrote:
Dear list,

I am using boost graph and I need to solve a variant of the classic
TSP.  Boost providess a function (metric_tsp_approx) to get a
Halmintonian cycle over a full connected metric weighted graph.
However I need something slightly different.

I need a path that visits all vertices starting and ending to two
well known vertices (let be s and d). Seeking around, I found the
suggestion of adding a node connected to s d and with the weight of
the edge (s,d). The TSP solution of the new graph is the solution,
just removing the new node.

The problem is that now the graph is not complete anymore so the
metric_tsp_approx's approach does not work anymore.

Another possiblity is using a variant of Christofides algorithm, but
one of the passages of that is the minimum weight perfect matching.

I am a little confused by the documentation of the functions about
Maximum Cardinality Matching(1), it is possible to use them to find
the a maximum cardinality matching so that the total weight of all
selected edges is minimal?

Otherwise, is there an alternate approach to my problem?

Yours faithfully,
Paolo

(1) http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/maximum_matching.html
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users