Research into Network Algorithms and Related Problems

本计划研究基本网络问题，包括最大、最小成本、多商品流问题、最短路径问题、最小切割问题和分配问题。这些都是具有许多应用的经典组合优化问题。从理论的角度来看，设计有效的算法和理解这些问题的组合结构非常重要，因为这些问题对该领域来说是非常基础的，从实践的角度来看，因为这些问题的实例需要解决。有兴趣将这项工作的结果扩展到相关问题，如线性规划。该研究有三个相互关联的组成部分：(1)第一部分涉及对这些问题的组合结构的更好理解；(2)第二部分涉及新算法的开发，以提高当前已知的问题复杂性界限；(3)第三部分涉及对现有算法和新开发算法的实验评估。最坏情况下的理论效率并不总是与实际效率相对应。现有的和新开发的算法对一些问题的实验评估是有趣的。实验研究还通过识别实现所需的子问题和数据结构以及通过提出可能比源自理论研究的原始变体更有效的算法变体来激励理论研究。

This project studies fundamental network problems, including maximum, minimum-cost, and multicommodity flow problems, shortest paths problems, minimum cut problems, and the assignment problem. These are classical combinatorial optimization problems that have numerous applications. Designing efficient algorithms and understanding combinatorial structure of these problems is important from a theoretical point of view because these problems are very basic to the field, and from a practical point of view because instances of these problems need to be solved. There is interest in extending the results of this work to related problems, such as linear programming. The research has three interrelated components: (1) the first involves a better understanding of combinatorial structure of these problems; (2) the second involves development of new algorithms that improve currently known bounds on the problem complexity; and (3) the third involves experimental evaluation of the currently existing and newly developed algorithms. The worst-case theoretical efficiency does not always correspond to practical efficiency. Experimental evaluation of existing and newly developed algorithms for some of the problems is of interest. The experimental research also motivates theoretical research by identifying subproblems and data structures needed by the implementations and by suggesting variations of algorithms which may be more efficient than the original variants originating in theoretical research.