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).