Re: [Boost-users] Minimum perfect matching

Subject: Re: [Boost-users] Minimum perfect matching
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2014-02-12 09:50:57

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_at_[hidden]> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>