A Randomized Parallel Branch-and-Bound Procedure

We present a universal randomized method called Local Best-First Search for parallelizing sequential branch-and-bound algorithms. The method executes on a message-passing multiprocessor system, and requires no global data structures or complex communication protocols. We show that, uniformly on all instances, the execution time of the method is unlikely to exceed a certain inherent lower bound by more than a constant factor.

Authors

• Richard M. Karp
• Yanjun Zhang

Keywords

No keywords are indexed for this paper.