Randomized Parallel Algorithms

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

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