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.//