CAREER: Algorithmic Methods for Networks

该研究计划以组合优化算法的设计和分析为中心，重点放在两个主要方向：开发有效的近似算法，为组合优化中的疑难问题提供接近最优的解；以及将这些技术用于大规模网络的算法设计。一个基本的目标是开发出逼近难解优化问题的最优解的一般方法。线性规划方法的研究已被证明是深入了解此类问题结构的一种有价值的方式。这项工作中的方法涉及基于线性规划及其一些推广的技术的发展，以及与概率方法和随机算法的结合。一个相关的问题是优化的局部搜索方法的行为，作为一种手段，理解它们所操作的可行解的“图景”；这个问题在一般层面上与生物分子结构领域的一些具体优化问题之间有着密切的联系。这些算法技术的一个丰富的应用领域，也是本研究的重点，是在网络优化问题领域。一个基本问题是路由业务流以使通信网络中的拥塞最小化的问题。这涉及来自网络流的技术，适用于虚电路路由的框架。这项研究中正在进行的另一个问题是开发工具来将网络流量作为一种动态现象进行分析，这种现象随着时间的推移不断到来。这里的一些基本问题是{\em稳定性}-确定网络中的延迟是否在长时间内保持有界-以及对其速率可能随时间大幅波动的流量的概率分析。该计划的教育部分侧重于计划开发一门课程，旨在将当前算法的发展与生物科学的工作联系起来。特别是，这里有一个新兴的机会，可以让计算机科学的学生以及生物和化学专业的学生围绕分子生物学中出现的一系列基本计算问题汇聚一堂。与此相关的是在核心本科算法课程中增加对某些主题的覆盖范围的计划：特别是优化中的启发式和局部搜索方法的一般领域，这在目前分子生物学和相关领域的许多计算工作中占据了突出地位。

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.***