Re: [Boost-users] Minimum perfect matching

Subject: Re: [Boost-users] Minimum perfect matching
From: Paolo Bolzoni (paolo.bolzoni.brown_at_[hidden])
Date: 2014-02-13 09:38:01

Dear list,
I read in the boost/graph/metric_tsp_approx.hpp source file that the
Christofides algorithm has been considered.

However the implementation of the blossom algorithm is the big
problem of such a task. Is anyone working on it?

Cheers,
Paolo

On Wed, Feb 12, 2014 at 4:15 PM, Paolo Bolzoni
<paolo.bolzoni.brown_at_[hidden]> wrote:
> Hi Aaron,
> I am afraid it won't work because the graph is not metric anymore.
> The metric_tsp_approx needs a metric graph because it shortcuts the
> minimum spanning tree; when it happens everything works because a ->
> b -> c is at most as long than a -> c. Adding the node (f) it can
> happen that the shortcut is from a -> b -> f to a -> f and the
> latter is one of this "infinity weight" edges.
>
> Cheers,
> Paolo
>
> On Wed, Feb 12, 2014 at 3:50 PM, Aaron Windsor <aaron.windsor_at_[hidden]> wrote:
>> 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
>>
>>
>>
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users