Networks, of all kinds, surround us in our modern existence. Telecommunications networks, road networks, social networks, flight connections, and even the circuits in the microprocessors in our computers and cellphones are just a few examples. Some fundamental network problems appear again and again in a variety of these settings, and better algorithms - and more importantly, keener insights - into these problems are needed. Many of these problems are algorithmically hard optimization problems, and we cannot expect optimal solutions in reasonable time. Instead, approximations must be accepted, and the aim is to provide the best possible guarantee efficiently.
The goal of this project is to explore new approaches and techniques for fundamental optimization problems, both new and old, in network design. The problems to be investigated include the classical traveling salesman problem, the problem of finding a tour of minimum length visiting all the nodes in a network, and the Steiner tree problem, which asks for the cheapest tree connecting some collection of terminals within a network. These problems have been intensively studied, but recently there has been some exciting progress. Two main techniques underlying this progress are the study of "thin" spanning trees, and advances in the design of strong rounding algorithms. In this project, the PIs aim to continue investigation in these directions with the hope of further breakthroughs. Another class of problems we consider relates to the quite practical issue of provisioning a network to handle varied and uncertain demands. This context has already demonstrated a combination of beautiful mathematical structure and important practical implications, and one of the goals of this project is to expand the class of such network design problems that can be efficiently solved.
Due to their fundamental nature, progress on these problems would have an immediate impact on the field, driving even further progress. There would also be a broader impact, with theoretical advancements aiding and guiding practical improvements in industry. In particular, part of the project will focus on recent models of demand patterns and capacity requirements in telecommunication networks. As bandwidth requirements increase rapidly, with the dramatic increase in video and multimedia, ways need to be found to more efficiently utilize network resources. Another central aspect of this project with broader impact is the training and mentoring of graduate students and junior researchers.
