Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:
10 Randomization in Parallel Algorithms
10 Randomization in Parallel Algorithms
Pages 149-160
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 149... ...
machine and has the property that an algorithm designed for it wiB perform without significant degradation on most commonly available parallel machines, including iThis work was supported in part by NSF grant CCR-89-10707.
|
From page 150... ...
The PRAM consists of a collection of independent sequential machines, each of which is caked a processor, that communicate with one another through a global memory. This is a synchronous model, and a step of a PRAM consists of a read cycle in which each processor can read a global memory cell, a computing cycle in which each processor can perform a unittime sequential computation, and a write cycle in which each processor can write into a gIobad memory cell.
|
From page 151... ...
10.3 The Randomized Parallel Complexity Class RNC In the design and analysis of highly parallel algorithms for various problems, it has been observed that some problems have simple highly paraDe] algorithms using a relatively small number of processors whereas others have resisted ad attempts so far to obtain any algorithm with a significant amount Of parallelism.
|
From page 152... ...
However, if we allow randomization, we can come up with a simple Monte CarIo algorithm for the problem, as shown below. The randomized algorithm is based on the following lemma, which is fairly straightforward to prove by induction on the number of variables n (note that the base case n = 1 follows from the fact that any single variable polynomial of degree n has at most n zeros)
|
From page 153... ...
The problem of finding a maximum matching in a graph is an important one and one that has received extensive attention in the context of sequential algorithm design. Although the problem is not known to be in NC, the above result allows us to find a maximum matching quickly and with high confidence.
|
From page 154... ...
We illustrate this simplifying potential of randomization with a problem that has received much attention in this context, the maximal independent set problem (Aloe et al., 1986; Karp and Wigierson, 1985; Ruby, 1986~. The problem of finding a maximal independent set in a graph has been studied extensively in the context of parallel algorithm design.
|
From page 155... ...
Although fast, efficient deterministic paraBel algorithms have been developed for this problem, these algorithms tend to be fairly complicated. On the other hand, the following simple randomized algorithm gives a fast parallel algorithm for the problem and is more efficient than any of the deterministic NC algorithms known for it.
|
From page 156... ...
This technique has proved to be a powerful one and has resulted in efficient determ~nistic NC algorithms for several problems using the technique of first constructing ~ efficient randomized paraded algorithm with limited independence and then transforming the randomized algorithm into a deterministic one (Berger and Rompel, 1989; Ruby, 1988; Motwani et al., 1989~. 10.7 Conclusion This chapter has described some of the most significant applications of randomization in paraBe!
|
From page 157... ...
30th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CaTif., 2-7. Borodin, A., S.A.
|
From page 158... ...
SOth Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, Calif., 8-13.
|
From page 159... ...
Reif (1989) , Optimal and sublogarithm~c time randomized parallel algorithms, SlA M ]
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.