Best-first branch-And-bound on a hypercube

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

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 languageEnglish (US)
Title of host publicationProceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988
EditorsGeoffrey Fox
PublisherAssociation for Computing Machinery, Inc
Pages1500-1504
Number of pages5
Volume2
ISBN (Electronic)0897912780, 9780897912785
DOIs
StatePublished - Jan 3 1989
Externally publishedYes
Event3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 - Pasadena, United States
Duration: Jan 19 1988Jan 20 1988

Other

Other3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988
CountryUnited States
CityPasadena
Period1/19/881/20/88

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Computer Graphics and Computer-Aided Design
  • Software
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Best-first branch-And-bound on a hypercube'. Together they form a unique fingerprint.

  • Cite this

    Felten, E. W. (1989). Best-first branch-And-bound on a hypercube. In G. Fox (Ed.), Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 (Vol. 2, pp. 1500-1504). Association for Computing Machinery, Inc. https://doi.org/10.1145/63047.63107