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.