Journal Article

FZJ-2016-03693

http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png The approximate solution of the Euclidean traveling salesman problem on a CRAY X-MP

Gurke, R. (Corresponding author)

1988
North-Holland, Elsevier Science Amsterdam [u.a.]

This record in other databases:    

Please use a persistent id in citations: doi:10.1016/0167-8191(88)90122-6

Abstract: The efficient use of MIMD computers calls for a careful choice of adequate algorithms as for an implementation taking into account the particular architecture. To demonstrate these facts, a parallel algorithm to find an approximate solution to the Euclidean Traveling Salesman Problem (ETSP) is presented. The algorithm is a parallelization of Karp's partitioning algorithm. It is a divide-and-conquer method for solving the ETSP approximately. Since the successor vertex to any vertex in the tour is usually a nearby vertex, the problem can be ‘geographically’ partitioned into subproblems which then can be solved independently. The resulting subtours can be combined into a single tour which is an approximate solution to the ETSP. The algorithm is implemented on a CRAY X-MP with two and four processors, and results using macrotasking and microtasking are presented.

---

Contributing Institute(s):

1. Zentralinstitut für Angewandte Mathematik (ZAM)
2. Jülich Supercomputing Center (JSC)

Research Program(s):

1. 899 - ohne Topic (POF3-899) (POF3-899)

---

Database coverage:
; Current Contents - Engineering, Computing and Technology ; IF < 5 ; JCR ; SCOPUS ; Science Citation Index Expanded ; Thomson Reuters Master Journal List ; Web of Science Core Collection

---