1988 · 83 citations · 6 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismParallel Algorithm DesignParallel ArchitecturesParallel Computer ArchitectureParallel Computing SystemsParallel SearchingBest-first SearchCommunication ProtocolsExecution Time AnalysisParallel Branch And BoundParallel Search AlgorithmsParallel Searching AlgorithmsRandomized Parallel AlgorithmsRandomized Parallel Search
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.
6
Branch-and-Bound Methods: A Survey
Eugene L. Lawler, Derek Wood · Operations Research · 1966 · 2K citations
Multiprocessing of Combinatorial Search Problems
Wah, Guojie Li, Chee Fen Yu · Computer · 1985 · 92 citations