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