Computer Sciences Seminar
Tuesday, March 5
12:30 PM, NAC 8/206

Designing Networks with Uncertainty in Demands

Anupam Gupta
Bell Labs

Abstract
Network Design is one of the fundamental areas of research in graph algorithms, with the past few years giving us many deep theoretical results as well as efficient heuristics.

An intriguing question in network design has been to try and capture the volatile nature of traffic, and to provision networks that are capable of handling not one, but a variety of traffic scenarios. A model that has been around for the past decade, and which has gained much popularity in recent years is the so-called "hose" model of Duffield et al., in which valid demands are implicitly defined by upper bounds on the traffic rate at each terminal, and the network must be designed to handle this continuum of traffic scenarios.

The model and its attendant questions focus attention on a set of natural but unexplored problems in network design; in this talk, we give algorithms with provable performance guarantees for some of these problems, and indicate directions for future research.

Bio
I got my Ph.D. in Computer Science from the University of California, Berkeley in Fall 2000, and have since been a postdoctoral researcher, first at Cornell University, and since Spring 2001, at Lucent Bell Labs, Murray Hill. My research interests are in theoretical computer science, and much of my recent work has been on designing algorithms for network design, and in the study of metric embeddings.