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