Research in Graph Algorithms and Combinatorial Optimization

摘要

This project focused on designing fast algorithms for basic combinationaloptimization problems, including maximum flow, matching, multicommodity flow, and generalized flow. Many important applications are naturally stated as variants of these problems, and hence improved algorithms for these problems immediately lead to improved algorithms for a wide variety of applications. Our goal was to improve both sequential and parallel complexity. In many applications, solving a multicommodity or a generalized flow problem is only a first step in approximately solving an NP-complete problem; in the majority of such cases there is no need to have an exact solution of the problem. One of the focuses of the project was design of efficient approximation algorithms.