# A Simpler Analysis of the Karp-Zhang Parallel Branch-and-Bound Method

### Abhiram Ranade

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-90-586

August 1990

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/CSD-90-586.pdf

Karp and Zhang presented a general method for deriving randomized parallel branch-and-bound algorithms from sequential ones. They showed that with high probability the resulting algorithms attained optimal speedup to within a constant factor, for large enough problems. We present an alternate analysis of their method. Our analysis is considerably simpler, and gives good bounds even for small problem sizes.

BibTeX citation:

@techreport{Ranade:CSD-90-586, Author = {Ranade, Abhiram}, Title = {A Simpler Analysis of the Karp-Zhang Parallel Branch-and-Bound Method}, Institution = {EECS Department, University of California, Berkeley}, Year = {1990}, Month = {Aug}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/6384.html}, Number = {UCB/CSD-90-586}, Abstract = {Karp and Zhang presented a general method for deriving randomized parallel branch-and-bound algorithms from sequential ones. They showed that with high probability the resulting algorithms attained optimal speedup to within a constant factor, for large enough problems. We present an alternate analysis of their method. Our analysis is considerably simpler, and gives good bounds even for small problem sizes.} }

EndNote citation:

%0 Report %A Ranade, Abhiram %T A Simpler Analysis of the Karp-Zhang Parallel Branch-and-Bound Method %I EECS Department, University of California, Berkeley %D 1990 %@ UCB/CSD-90-586 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/6384.html %F Ranade:CSD-90-586