CaltechAUTHORS
  A Caltech Library Service

Best-first branch-and-bound on a hypercube

Felten, Edward W. (1988) Best-first branch-and-bound on a hypercube. In: C3P Proceedings of the third conference on Hypercube concurrent computers and applications. Vol.2. ACM , New York, NY, pp. 1500-1504. ISBN 0-89791-278-0. http://resolver.caltech.edu/CaltechAUTHORS:20161013-134329569

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20161013-134329569

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/63047.63107DOIPaper
http://dl.acm.org/citation.cfm?doid=63047.63107PublisherPaper
Additional Information:© 1988 ACM.
Record Number:CaltechAUTHORS:20161013-134329569
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20161013-134329569
Official Citation:E. W. Felten. 1989. Best-first branch-and bound on a hypercube. In Proceedings of the third conference on Hypercube concurrent computers and applications - Volume 2 (C3P), Geoffrey Fox (Ed.), Vol. 2. ACM, New York, NY, USA, 1500-1504. DOI=http://dx.doi.org/10.1145/63047.63107
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71064
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:13 Oct 2016 21:03
Last Modified:13 Oct 2016 21:03

Repository Staff Only: item control page