A Simpler Analysis of the Karp-Zhang Parallel Branch-and-Bound Method
Abhiram Ranade · UC Berkeley · 1990
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