Randomized Parallel Algorithms

虽然随机化在算法设计中的作用还没有被完全理解，但使用随机化已经很好地解决了几个重要的计算问题。对于各种问题，最著名的随机化算法比其确定性算法具有更好的资源边界。这项持续的研究项目通过研究随机化在设计几个计算问题的并行算法中的作用来解决更好地理解随机化的问题，这些问题包括(1)排序和选择、(2)分组路由和(3)计算几何。这些采样和算法工具在自然语言处理、计算机模拟和运动规划等不同领域的最优(或接近最优)并行算法的设计中的应用也被考察。

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.