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.