CAREER: Algorithmic Methods for Networks

职业：网络算法方法

• 批准号: 9701399
• 负责人: Jon Kleinberg
• 金额: $ 20万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-04-01 至 2002-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9701399&HistoricalAwards=false
• 关键词: CAREER; Algorithmic; Methods; Networks

The research program is centered around the design and analysis of algorithms in combinatorial optimization, with an emphasis in two major directions: the development of efficient approximation algorithms to provide near-optimal solutions to intractable problems in combinatorial optimization; and the use of these techniques in the design of algorithms for large-scale networks. A fundamental goal is the development of general methods for approximating the optimal solutions to intractable optimization problems. The study of linear programming methods has proved to be a valuable way to gain insight into the structure of such problems. The approach in this work involves the development of techniques based on linear programming and some of its generalizations, in conjunction with probabilistic methods and randomized algorithms. A related issue is the behavior of local-search methods for optimization, as a means of understanding the ``landscape'' of feasible solutions on which they operate; there are close connections between this issue at a general level and some concrete optimization questions in the area of biomolecular structure. A rich application area for these algorithmic techniques, and the focus of much of this research, is in the area of network optimization problems. One basic issue is the problem of routing traffic streams so as to minimize congestion in communication networks. This involves techniques from network flows, adapted to the framework of virtual circuit routing. Another on-going issue in this research is the development of tools to analyze network traffic as a dynamic phenomenon, which arrives continuously over time. Some fundamental issues here are {\em stability} --- determining whether delays in the network remain bounded over long durations --- and the probabilistic analysis of traffic whose rate can fluctuate greatly over time. The education component of the program is focused on the planned development of a course designed to link curren t developments in algorithms with work in the biological sciences. In particular, there is an emerging opportunity here to bring together students from computer science, and those in biology and chemistry, around the set of fundamental computational problems that have arisen in molecular biology. Related to this is a plan for increased coverage of certain topics in the core undergraduate algorithms course: in particular, the general area of heuristic and local-search methods in optimization, which has figured prominently in much of the computational work currently being done in molecular biology and related areas.***

该研究项目以组合优化算法的设计和分析为中心，重点关注两个主要方向：开发高效的近似算法，为组合优化中的棘手问题提供近乎最优的解决方案；以及这些技术在大规模网络算法设计中的使用。一个基本目标是开发通用方法来近似棘手优化问题的最佳解决方案。线性规划方法的研究已被证明是深入了解此类问题结构的宝贵途径。这项工作中的方法涉及基于线性规划及其一些概括的技术的开发，以及概率方法和随机算法。一个相关的问题是本地搜索优化方法的行为，作为理解其运行的可行解决方案“景观”的一种手段；这个一般层面的问题与生物分子结构领域的一些具体优化问题之间存在着密切的联系。这些算法技术的丰富应用领域以及本研究的重点是网络优化问题领域。 一个基本问题是路由流量的问题，以尽量减少通信网络中的拥塞。这涉及来自网络流的技术，适应虚电路路由的框架。这项研究中另一个正在进行的问题是开发工具来分析网络流量作为一种动态现象，随着时间的推移不断到达。这里的一些基本问题是稳定性——确定网络中的延迟是否在长时间内保持有限状态——以及速率可能随时间大幅波动的流量的概率分析。该计划的教育部分重点是计划开发一门课程，旨在将算法的当前发展与生物科学的工作联系起来。 特别是，这里有一个新兴的机会，可以将计算机科学以及生物学和化学专业的学生聚集在一起，围绕分子生物学中出现的一系列基本计算问题。 与此相关的是一项计划，旨在增加核心本科算法课程中某些主题的覆盖范围：特别是优化中的启发式和局部搜索方法的一般领域，这在分子生物学和相关领域目前正在进行的许多计算工作中占据着显着的地位。***