Research into Network Algorithms and Related Problems

网络算法及相关问题研究

• 批准号: 9307045
• 负责人: Serge Plotkin
• 金额: $ 22.27万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-05-01 至 1998-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9307045&HistoricalAwards=false
• 关键词: Research; into; Network; Algorithms; Related

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.

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