Nick Lai and Barton P. Miller

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-84-212
December 1984

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-212.pdf

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.

BibTeX citation:

@techreport{Lai:CSD-84-212,
    Author = {Lai, Nick and Miller, Barton P.},
    Title = {The Traveling Salesman Problem: The Development of a Distributed Computation},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1984},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5924.html},
    Number = {UCB/CSD-84-212},
    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.  <p>  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.}
}

EndNote citation:

%0 Report
%A Lai, Nick
%A Miller, Barton P.
%T The Traveling Salesman Problem: The Development of a Distributed Computation
%I EECS Department, University of California, Berkeley
%D 1984
%@ UCB/CSD-84-212
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5924.html
%F Lai:CSD-84-212