Abhiram Ranade

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-90-586

, 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},
    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