Randomness and Parallelism in Algorithms

算法中的随机性和并行性

• 批准号: 8912063
• 负责人: George Lueker
• 金额: $ 11.4万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-10-01 至 1992-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8912063&HistoricalAwards=false
• 关键词: Randomness; Parallelism; Algorithms

This project investigates the role of randomness and parallelism. Specific problems involving the behavior of algorithms with random input include hashing, packing, and partitioning algorithms. With respect to parallel computation, the PI (with Megiddo and Ramachandran) showed that linear programming with two variables per constraint (and in the objective function) is solvable in polylog space. This project investigates whether it is in NC (or possibly RNC), along with variations of the problem, and their relation to problems such as matching. Also under investigation is the reduction of the processor count in parallel algorithms. Of particular interest are problems such as path-finding in directed graphs, and special cases such as planar graphs.

这个项目探讨了随机性和并行性的作用。涉及随机输入算法行为的具体问题包括散列、打包和分区算法。关于并行计算，PI（与Megiddo和Ramachandran）表明，每个约束（和目标函数）具有两个变量的线性规划在多对数空间中是可解的。这个项目调查了它是否在NC（或可能是RNC）中，以及问题的变化，以及它们与匹配等问题的关系。在并行算法中减少处理器数量也在研究之中。特别感兴趣的是有向图中的寻路问题，以及像平面图这样的特殊情况。