Published January 1988
| public
Book Section - Chapter
Best-first branch-and-bound on a hypercube
- Creators
- Felten, Edward W.
- Other:
- Fox, Geoffrey
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.
Additional Information
© 1988 ACM.Additional details
- Eprint ID
- 71064
- Resolver ID
- CaltechAUTHORS:20161013-134329569
- Created
-
2016-10-13Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field