Randomized Parallel Algorithms

虽然随机化在算法设计中的作用还没有被完全理解，但一些重要的计算问题已经用随机化优雅地解决了。对于各种问题，最著名的随机算法比它们的确定性对应物具有更好的资源边界。该研究通过研究随机化在三个关键计算问题(1)排序和选择，2)分组路由和3)组合优化)并行算法设计中的功能，解决了更好地理解随机化的问题。针对这三个问题，我们将在不同的并行计算模型上设计最优或接近最优的并行算法。该项目开发的采样和算法工具将在自然语言处理、计算机仿真、运动规划等不同领域得到应用

While the role of randomization in algorithms 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. The research addresses the issue of a better understanding of randomization, by studying its function in the design of parallel algorithms for three critical computing problems, 1) Sorting and Selection, 2) Packet Routing, and 3) Combinatorial Optimization. Optimal or near optimal parallel algorithms for these three problems on various models of parallel computing will be designed. Sampling and algorithmic tools developed in this project will find applications in such diverse areas as natural language processing, computer simulation, motion planning, etc.//