Boost logo

Boost Users :

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.

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


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at