Re: [Boost-users] Metric_TSP_approx example

Subject: Re: [Boost-users] Metric_TSP_approx example
From: Anders Wallin (anders.e.e.wallin_at_[hidden])
Date: 2012-03-20 16:55:06

>> The metric_tsp_approx_tour give the result: 0,3,1,2,4,5,0.
>> I think 0,3,1,2,5,4,0 is better than the previous result, am I wrong?
>>
>
> It could be.  metric_tsp_approx is only an
> approximation.

the algorithm in metric_tsp_approx ensures a tour which is at most
twice the length of the optimal tour.
I ran it on a few of the TSPLIB datasets, and in practice the results
seem to cluster around 1.4-times the optimal tour length.
http://www.anderswallin.net/wp-content/uploads/2011/05/tsp_on_i71.png

The Christofides heuristic would guarantee guarantees a tour at most
1.5x the optimal tour. That requires a minimum weight perfect matching
algorithm.

Anders