The Role of Approximation and Parallelism in Solving Graph Problems Quickly

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

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.