@inproceedings{3785015fcdc14139b4f54dc1b6681c6f,
title = "Best-first branch-And-bound on a hypercube",
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.",
author = "Felten, {Edward W.}",
note = "Publisher Copyright: {\textcopyright} ACM 1988 0-89791-278-0/88/0007/1592.; 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 ; Conference date: 19-01-1988 Through 20-01-1988",
year = "1989",
month = jan,
day = "3",
doi = "10.1145/63047.63107",
language = "English (US)",
series = "Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, C3P 1988",
publisher = "Association for Computing Machinery, Inc",
pages = "1500--1504",
editor = "Geoffrey Fox",
booktitle = "Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988",
}