Abstract
The branch-And-bound technique is a common method for finding exact solutions to difficult problems in combinatorial optimization. This paper will discusss issues surrounding implementation of a particular branch-And-bound algorithm for the traveling-salesman problem on a hypercube multicomputer. The natural parallel algorithm is based on a number of asynchronous processes which interact through a globally shared list of unfinished work. In a distributed-memory environment, we must find a non-centralized version of this shared data structure. In addition, detecting termination of the computation is tricky; an algorithm will be presented which ensures proper termination. Finally, issues affecting performance will be discussed.
Original language | English (US) |
---|---|
Title of host publication | Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 |
Editors | Geoffrey Fox |
Publisher | Association for Computing Machinery, Inc |
Pages | 1500-1504 |
Number of pages | 5 |
Volume | 2 |
ISBN (Electronic) | 0897912780, 9780897912785 |
DOIs | |
State | Published - Jan 3 1989 |
Externally published | Yes |
Event | 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 - Pasadena, United States Duration: Jan 19 1988 → Jan 20 1988 |
Other
Other | 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 |
---|---|
Country/Territory | United States |
City | Pasadena |
Period | 1/19/88 → 1/20/88 |
All Science Journal Classification (ASJC) codes
- Hardware and Architecture
- Computer Graphics and Computer-Aided Design
- Software
- Computer Science Applications