From: Morton Goldberg <m_goldberg@...>
Date: 2007-10-07T10:30:49+09:00
Subject: Re: [QUIZ] Itinerary for a Traveling Salesman (#142)

On Oct 6, 2007, at 4:05 PM, Eric Mahurin wrote:

> On 10/5/07, Ruby Quiz <james@grayproductions.net> wrote:
>> Second, let's relax the requirement that the itinerary be truly  
>> minimal. Let's
>> only require that it be nearly minimal, say, within 5%. Now you  
>> can tackle the
>> problem with one of several heuristic optimization algorithms  
>> which run in
>> polynomial time.  In particular, you could use a genetic algorithm  
>> (GA).
>
> As far as I know, a genetic algorithm isn't going to guarantee any
> approximation factor (within 1.05 of optimal as suggested above),
> right?  To get that kind of guaranteed accuracy level, I think you'd
> need to go with  Arora's quite complex polynomial-time approximation
> scheme, which I have yet to see an implementation of.  Personally, I'd
> like to see it implemented for the (rectilinear) steiner tree problem
> (his techniques work on a whole slew of geometric graph problems).

You are correct. For the general shortest tour problem, a genetic  
algorithm can't guarantee a solution within a specific error bound. I  
should have been clearer about that.

However, for the grid version of the problem with the grid not too  
big (say, n x n <= 10 x 10), it is not at all hard to come up with a  
genetic algorithm that meets the 5% goal. And how many salesmen make  
trips with more than 100 cities on their itinerary? :)

I really don't want this quiz to be too hard. I don't expect anyone  
participating in this quiz to work with really large grids. A  
solution that can get to within 5% on a 10 x 10 grid is a good one as  
far as I'm concerned.

Regards, Morton