Anupam Gupta

Adjunct Faculty

Website

Email ag@andrew.cmu.edu

Department
Computer Science Department

Research Interests
Algorithms and Complexity
Artificial Intelligence
Theory

Advisees
Madhusudhan Pittu

My main research interests are in Network Design and Metric Embeddings; I also work on Approximation and Graph algorithms.

Network Design and Optimization. Given a graph and a collection of userswho want to communicate with each other, the aim of network design is toprovision "good" networks satisfying the communication requirements. Asstated, things are still underspecified, and lead to many questions: e.g., what are the criteria for goodness? Are the networks capacitated?What is the cost model for allocating bandwidth? Are we routing paths (as in telephone calls), or can we deal with traffic as flows (as in packet routing)? What do communication requirements look like, and how are they specified? Furthermore, things are made more complicated by the fact that data is often not available beforehand---how does one handle uncertainity? I have been working on modeling and designing provably good algorithms for some of the problems arising from these issues. In particular, I have been working on handling uncertainity in data, and on designing networks for cost models that incorporate economies of scale.

Metric Embeddings. The goal of this area is to study the structure of metric spaces, and to use this understanding in the design of algorithms for a variety of problems arising on metrics. The approach to expose the inherent structure of metrics is to map the metric into a conceptually "simpler" metric that can be used in algorithmic applications in lieu of the original metric; of course, the new simpler metric should resemble the given metric, and hence the map should not distort distances by too much. For instance, if we wanted to solve the travelling salesman problem on a metric space, and we could map the metric into a tree changing the distances by only 10%, then we could solve the TSP on the simpler metric optimally, and this would be within 10% of the optimal solution on the original graph. In recent years, embeddings have become an indispensible tool in the algorithm designer's toolbox, being very powerful and versatile; they have been used for geometric algorithms, finding good graph separators, online algorithms, network design, data structures and many other applications. Despite these successes, many fundamental problems remain open in the area, including understanding how well given metrics can be embedded into Euclidean and other normed spaces; how given data sets can be embedded into low-dimensional spaces without distorting distances substantially; how the topology of graphs interacts with their metric properties, etc. All this research proceeds hand in hand with the algorithmic applications, primarily to providing approximation algorithms for a variety of problems on graphs.

Publications