Research in Graph Algorithms and Combinatorial Optimization

图算法与组合优化研究

• 批准号: 9008226
• 负责人: Serge Plotkin
• 金额: $ 4.12万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-09-01 至 1993-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9008226&HistoricalAwards=false
• 关键词: Research; Graph; Algorithms; Combinatorial; Optimization

This project focuses on design of efficient algorithms for combinatorial optimization problems. Many efficient parallel algorithms were obtained as a result of a deeper understanding of combinatorial structure of the problems, and therefore the emphasis of this research is to combine the work on improving the parallel/distributed complexity of the algorithms with the work on improving their sequential complexity. In particular, the research concentrates on finding efficient parallel deterministic algorithms for the class of problems related to bipartite matching and on finding efficient sequential algorithms for problems related to generalized flow and multicommodity flow. Another important part of this research is to develop techniques that allow transformation of efficient parallel algorithms into algorithms that are efficient in the context of distributed computation.

该项目的重点是设计有效的算法， 组合优化问题。 许多有效的并行 算法是由于对以下内容有了更深入的理解而获得的： 问题的组合结构，因此强调 本研究是将联合收割机的工作与提高 并行/分布式算法的复杂性与工作 提高了它们的顺序复杂度。 特别是，研究 致力于寻找高效的并行确定性算法 对于与二分匹配相关的一类问题， 广义线性规划问题的有效序列算法 多商品流动。 这项研究的另一个重要部分 是开发技术， 将并行算法转化为在上下文中有效的算法 分布式计算。