Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!bloom-beacon!husc6!yale!root
From: root@yale.UUCP (Celray Stalk)
Newsgroups: comp.ai.neural-nets
Subject: Re: implementation of "traveling salesman algorithm" on connection machine
Summary: I don't think so
Keywords: TSP, connection machine
Message-ID: <49632@yale-celray.yale.UUCP>
Date: 3 Feb 89 23:44:20 GMT
References: <1637@cps3xx.UUCP>
Reply-To: berryman-harry@CS.YALE.EDU (Harry Berryman)
Distribution: usa
Organization: Yale University Computer Science Dept, New Haven CT  06520-2158
Lines: 21

In article <1637@cps3xx.UUCP> artzi@cpsvax.cps.msu.edu (Ytshak Artzi - CPS) writes:
>
>   Does anyone know about any implementation of efficient
>algorithms for the Traveling salesman Problem (TSP) on the
>Connection Machine ?

Anyone who answers that question "Yes" is not telling the truth. The
TSP is known to take at least exponential time, CM or no CM. It is also
not clear to me that the CM is a good machine for this problem. 
Using a massively parallel SIMD machine for a branch-and-bound 
problem usually means leaving a great many of the processors idle.
Any simulated annealing or nueral-net method would require the use
of the general router on the CM (to deal with  an arbitrary weighted graph)
and that would be very slow. The CM is awful  at communication 
that cannot be mapped to a N-dimensional grid.

                  H. Scott Berryman
                  Yale U. Computer Science Dept.
                  51 Prospect St.
                  New Haven, CT 06520