A randomized parallel branch-and-bound procedure

Richard M. Karp, Yanjun Zhang

1988 · 83 citations · 6 references

DOIFull text

Open access

Concepts

Abstract

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.

References

6