UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-84-212.pdf
Oskicat catalog record
Conditions of Use

Archive Home Page

The Traveling Salesman Problem: The Development of a Distributed Computation

Authors:
Lai, Nick
Miller, Barton P.
Technical Report Identifier: CSD-84-212
December 1984
CSD-84-212.pdf

Abstract: The Traveling Salesman Problem (TSP) is computationally expensive to evaluate. It can, however, be readily decomposed into subproblems that can be computed in parallel. Developing a distributed program taking advantage of such a decomposition, however, remains a difficult problem.

We developed such a distributed program to compute the TSP solutions, using a new set of distributed program performance tools to better understand our TSP program. These tools allowed us to discover the performance bottlenecks in our program and to revise the program to significantly improve its execution speed.