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.