David B. Shmoys

Professor
shmoys@cs.cornell.edu http://www.cs.cornell.edu/home/shmoys/shmoys.html
Ph.D. University of California, Berkeley, 1984

The primary focus of my research is on the design and analysis of efficient algorithms for discrete optimization problems, and in particular, on approximation algorithms for NP-hard problems.

Computational complexity theory provides a mathematical foundation for the intractability of many computational problems by proving that all NP-complete problems are equally hard. However, in practice, real-world inputs for some NP-hard optimization problems are straightforward to solve, whereas for others, even quite modestly sized inputs are beyond the limits of the most sophisticated methods. Analogously, from a theoretical perspective, for some NP-hard optimization problems it is possible to efficiently compute solutions that are guaranteed to be arbitrarily close to optimal, whereas for others, computing even a crude approximation to the optimum is also NP-hard. In fact, the extent to which such approximation algorithms exist for a problem provides a surprisingly accurate theoretical yardstick for its actual computational difficulty.

Our work has been motivated by the fact that certain linear programming relaxations have been shown to provide extremely good lower bounds on typical data. We provided a theoretical understanding of the strength of these bounds by designing algorithms that “round” the fractional solutions to these linear programs to nearby integer solutions without degrading the quality of the solution too much. We have been investigating a variety of clustering problems, and in joint work with Moses Charikar, Sudipto Guha, and Eva Tardos, we have obtained the first constant factor approximation algorithm for the k-median problem. We have also obtained improved approximation algorithms for the uncapacitated facility location problem (in joint work with Fabian Chudak), and for a variety of more general multi-level facility location problems (in joint work with Karen Aardal and F. Chudak, and with Nathan Edwards). For the former problem, not only is the theoretical performance of our algorithm surprisingly good, but it is more effective in practice than all previously known heuristic procedures for this problem. We have also been investigating the application of some of these rounding methods to problems arising in computational genomics, in joint work with Ph.D. student Dan Brown and the group in Plant Sciences at Cornell working under Steve Tanksley. The resulting software for computing genetic linkage maps has already seen widespread application within the genomics community.

[On sabbatical leave 1999-2000.]

University Activities

Member: Search Committee for Associate Dean for Undergraduate Studies, College of Engineering.

Professional Activities

Editor-in-Chief: SIAM Journal on Discrete Mathematics.

Editor: SIAM Journal on Computing.

Co-Editor: SIAM/MPS Series on Optimization.

Associate Editor: Mathematics of Operations Research; Mathematical Programming; Journal of Scheduling.

Program Committee Chair: 11th ACM-SIAM Symposium on Discrete Algorithms (SODA).

Co-Organizer: Fields Institute Workshop on Approximation Algorithms.

Council Member: Mathematical Programming Society.

Lectures

Optimization Methods in Computing Genetic Linkage Maps. IBM Watson Research Center, Yorktown Heights, NY, July 1999.

Approximation algorithms for scheduling problems. UC Berkeley, CS Theory Seminar, Berkeley, CA, October 1999.

—. Invited tutorial. IBM Watson Research Center, Yorktown Heights, NY, July 1999.

Approximation algorithms for clustering problems. Invited plenary lecture. 12th Annual Conference on Computational Learning Theory (COLT 99), University of California at Santa Cruz, Santa Cruz, CA, July 1999.

—. Distinguished Lecturer Series. University of Southern California Dept. of Computer Science, Los Angeles, CA, February 2000.

Approximation algorithms via linear programming. IEOR Colloquium. UC Berkeley, Berkeley, CA, February 2000.

—. IBM Almaden Research Center, Almaden, CA, May 2000.

A constant-factor approximation algorithm for the k-median problem. Dagstuhl Workshop on randomization methods in combinatorial optimization, January 2000.

—. International Symposium on Mathematical Programming, Atlanta, GA, August 2000.

Publications

“A constant-factor approximation algorithm for the k-median problem.” Proceedings of the 31st Annual ACM Symposium on Theory of Computing (1999), 1–10 (with M. Charikar, S. Guha, and E. Tardos).

“Improved approximation algorithms for the k-level facility location problem.” Information Processing Letters 72 (1999), 161–167 (with K. Aardal and F.A. Chudak).

“Selective mapping: a strategy for optimizing the construction of high-density linkage maps.” Genetics 155 (2000), 407–420 (with T.J. Vision, D.G. Brown,