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.