RANDOMIZED PARALLEL ALGORITHMS FOR BACKTRACK SEARCH AND BRANCH-AND-BOUND COMPUTATION

Universal randomized methods for parallelizing sequential backtrack se arch and branch-and-bound computation are presented. These methods exe cute on message-passing multiprocessor systems, and require no global data structures or complex communication protocols. For backtrack sear ch, it is shown that, uniformly on all instances, the method described in this paper is likely to yield a speed-up within a small constant f actor from optimal, when all solutions to the problem instance are req uired. For branch-and-bound computation, it is shown that, uniformly o n all instances, the execution time of this method is unlikely to exce ed a certain inherent lower bound by more than a constant factor. Thes e randomized methods demonstrate the effectiveness of randomization in distributed parallel computation.