The Role of Approximation and Parallelism in Solving Graph Problems Quickly

近似和并行性在快速解决图问题中的作用

• 批准号: 9012357
• 负责人: Philip Klein
• 金额: $ 4.64万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-07-01 至 1992-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9012357&HistoricalAwards=false
• 关键词: Role; Approximation; Parallelism; Solving; Graph

This project has three parts. Part one consists in developing new parallel graph algorithms that are efficient in their use of processors. The focus is on developing algorithmic building blocks that are useful in combinatorial optimization, e.g. shortest paths. Part two consists in obtaining new approximation algorithms for problems that are too difficult to solve exactly. Two such problems are finding a minimum-weight collection of edges in a graph whose deletion yields a planar graph, and finding a minimum number of edges to add to a graph to make it chordal. The first problem arises in planning the layout of a manufacturing facility, the second problem in solving sparse linear systems and linear programs. Part three consists in developing improved algorithms for variants of multicommodity flow, a problem that arises in the above approximation algorithms as well as in a variety of network analysis problems.

该项目有三个部分。 第一部分是开发新的 并行图算法，在他们的使用效率高， 处理器. 重点是开发算法构建模块 这在组合优化中是有用的，例如最短路径。 第二部分包括获得新的近似算法， 太难而无法精确解决的问题。 两个这样的问题 在一个图中找到一个最小权的边集合， 删除产生一个平面图，并找到最小数量的边缘 添加到图表中使其成为弦。 第一个问题出现在 规划制造设施的布局，第二个问题， 求解稀疏线性系统和线性规划。 第三部分 在于开发改进的算法， 多商品流动，在上述近似中出现的问题 算法以及各种网络分析问题。