Abhiram Ranade

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-90-586
August 1990

http://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/6384.html
%F Ranade:CSD-90-586