Re: [Boost-users] BGL Traveling Salesman Approximation

Subject: Re: [Boost-users] BGL Traveling Salesman Approximation
From: Anders Wallin (anders.e.e.wallin_at_[hidden])
Date: 2011-06-29 08:48:27

> and the solution it gave was:
> 0 1 2 3 5 7 9 11 13 15 16 18 20 21 23 25 26 28 30 32 35 37 40 39 38 36
> 34 33 31 29 27 24 22 4 6 8 10 12 14 17 19 0
> Is there anyway I can "fix" this solution?

FWIW I am getting the exact same solution (tour length 120.54).
The heuristic in BGL only guarantees a solution within 2x of the
optimal solution.
The 'smarter' Christofides heuristic would guarantee a solution within
1.5x of optimal.

I ran metirc_tsp_approx on some of the tsplib problems a while ago:
http://www.anderswallin.net/2011/05/tsp/
(I didn't investigate the O(N²*log(N)) vs. O(N²) issue any further...)

Anders