Research in Graph Algorithms and Combinatorial Optimization

本课题主要研究组合优化问题的有效算法设计。由于对问题的组合结构有了更深入的了解，得到了许多高效的并行算法，因此本研究的重点是将提高算法的并行/分布复杂度与提高算法的顺序复杂度相结合。特别是，研究集中于寻找与二部匹配相关的一类问题的有效并行确定性算法，以及与广义流和多商品流相关的问题的有效顺序算法。本研究的另一个重要部分是开发允许将高效并行算法转换为分布式计算环境下高效算法的技术。

This project focuses on design of efficient algorithms for combinatorial optimization problems. Many efficient parallel algorithms were obtained as a result of a deeper understanding of combinatorial structure of the problems, and therefore the emphasis of this research is to combine the work on improving the parallel/distributed complexity of the algorithms with the work on improving their sequential complexity. In particular, the research concentrates on finding efficient parallel deterministic algorithms for the class of problems related to bipartite matching and on finding efficient sequential algorithms for problems related to generalized flow and multicommodity flow. Another important part of this research is to develop techniques that allow transformation of efficient parallel algorithms into algorithms that are efficient in the context of distributed computation.