Access Restriction

Author Sahni, Sartaj ♦ Lai, Ten-Hwang
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Anomalous behavior ♦ Branch-and-bound ♦ Parallel algorithms
Abstract We consider the effects of parallelizing branch-and-bound algorithms by expanding several live nodes simultaneously. It is shown that it is quite possible for a parallel branch-and-bound algorithm using n2 processors to take more time than one using n1 processors, even though n1 < n2. Furthermore, it is also possible to achieve speed-ups that are in excess of the ratio n2/n1. Experimental results with the 0/1-Knapsack and Traveling Salesman problems are also presented.
Description Affiliation: Univ. of Minnesota, Minneapolis (Sahni, Sartaj) || Ohio State Univ., Columbus (Lai, Ten-Hwang)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 27
Issue Number 6
Page Count 9
Starting Page 594
Ending Page 602

Open content in new tab

   Open content in new tab
Source: ACM Digital Library