Yanjun Zhang

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-89-543

, 1989

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/CSD-89-543.pdf

This thesis is a theoretical study of parallel algorithms for combinatorial search problems. In this thesis we present parallel algorithms for backtrack search, branch-and-bound computation and game-tree search. <p>Our model of parallel computation is a network of processors communicating via messages. Our primary interest in a parallel algorithm is its speed-up over the sequential ones. Our goal is to design parallel algorithms that achieve a speed-up proportional to the number of processors used. <p>We first study backtrack search that enumerates all solutions to a combinatorial problem. We propose a simple randomized method for parallelizing sequential backtrack search algorithms for solving enumeration problems. We show that, uniformly on all instances, this method is likely to achieve a nearly best possible speed-up. <p>We then study the branch-and-bound method for solving combinatorial optimization problems. We present a randomized method called Local Best-First Search for parallelizing sequential branch-and-bound algorithms. We show that, uniformly on all instances, the execution time of this method is unlikely to exceed a certain inherent lower bound by more than a constant factor. <p>In the rest of this thesis we study the problem of evaluation of game trees in parallel. We present a class of parallel algorithms that parallelize the "left-to-right" algorithm for evaluating AND/OR trees and the Alpha-Beta pruning algorithm for evaluating MIN/MAX trees. We prove that the algorithm achieves a linear speed-up over the left-to-right algorithm on uniform AND/OR trees when the number of processors used is close to the height of the input tree. We conjecture that the same conclusion holds for the speed-up of the algorithm over the Alpha-Beta pruning algorithm.

Advisors: Richard M. Karp

---

BibTeX citation:

@phdthesis{Zhang:CSD-89-543,
    Author= {Zhang, Yanjun},
    Title= {Parallel Algorithms for Combinatorial Search Problems},
    School= {EECS Department, University of California, Berkeley},
    Year= {1989},
    Month= {Nov},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5909.html},
    Number= {UCB/CSD-89-543},
    Abstract= {This thesis is a theoretical study of parallel algorithms for combinatorial search problems. In this thesis we present parallel algorithms for backtrack search, branch-and-bound computation and game-tree search. <p>Our model of parallel computation is a network of processors communicating via messages. Our primary interest in a parallel algorithm is its speed-up over the sequential ones. Our goal is to design parallel algorithms that achieve a speed-up proportional to the number of processors used. <p>We first study backtrack search that enumerates all solutions to a combinatorial problem. We propose a simple randomized method for parallelizing sequential backtrack search algorithms for solving enumeration problems. We show that, uniformly on all instances, this method is likely to achieve a nearly best possible speed-up. <p>We then study the branch-and-bound method for solving combinatorial optimization problems. We present a randomized method called Local Best-First Search for parallelizing sequential branch-and-bound algorithms. We show that, uniformly on all instances, the execution time of this method is unlikely to exceed a certain inherent lower bound by more than a constant factor. <p>In the rest of this thesis we study the problem of evaluation of game trees in parallel. We present a class of parallel algorithms that parallelize the "left-to-right" algorithm for evaluating AND/OR trees and the Alpha-Beta pruning algorithm for evaluating MIN/MAX trees. We prove that the algorithm achieves a linear speed-up over the left-to-right algorithm on uniform AND/OR trees when the number of processors used is close to the height of the input tree. We conjecture that the same conclusion holds for the speed-up of the algorithm over the Alpha-Beta pruning algorithm.},
}

EndNote citation:

%0 Thesis
%A Zhang, Yanjun 
%T Parallel Algorithms for Combinatorial Search Problems
%I EECS Department, University of California, Berkeley
%D 1989
%@ UCB/CSD-89-543
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5909.html
%F Zhang:CSD-89-543