Randomized Parallel Algorithms

点击翻译按钮获取中文摘要

While the role of randomization in algorithm design has not been fully understood, several important computational problems have been solved elegantly using randomization. The best known randomized algorithms for a variety of problems have better resource bounds than their deterministic counterparts. This continuing research project addresses the issue of better understanding randomization, by studying its function in the design of parallel algorithms for several computing problems, including those in the areas of (1) sorting and selection, (2) packet routing, and (3) computational geometry. Applications of these sampling and algorithmic tools to the design of optimal (or near optimal) parallel algorithms in such diverse areas as natural language processing, computer simulation, and motion planning, are also examined.