David B. Shmoys
Professor
shmoys@cs.cornell.edu
http://www.cs.cornell.edu/home/shmoys/shmoys.html
PhD UC 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 NPhard problems.
Computational complexity theory provides a mathematical foundation for the intractability of many computational problems by proving that all NPcomplete problems are equally hard. However, in practice, realworld inputs for some NPhard 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
NPhard 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 optimumis also NPhard. 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
kmedian problem. We have also
obtained improved approximation
algorithms for both the uncapacitated and capacitated facility location
problems. For the former, not only is
the theoretical performance of the
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.
University Activities

Chair: Committee on Academic
Standards, Petitions, and
Credits (ASPAC), College of
Engineering

Admissions Committee:
Computer Science
 Common Curriculum Governing
Board
 Search Committee for Associate
Dean for Professional
Development, College of
Engineering

Search Committee for Associate
Dean for Undergraduate
Studies, College of Engineering
Professional Activities

EditorinChief: SIAM Journal
Discrete Mathematics
 Editor: SIAM Journal
Computing
 Associate Editor: Mathematics
of Operations Research, Mathematical Programming,
Journal Scheduling
 Program Committee Chair: 11thACMSIAM Symposium on
Discrete Algorithms (SODA)
 Program Committee Member:
40th Annual IEEE Symposium
on Foundations of Computer
Science (FOCS); 7th Integer
Programming and Combinatorial Optimization Conf. (IPCO)
 CoOrganizer: Fields Institute
Workshop on Approximation
Algorithms

Council Member: Mathematical
Programming Society
Lectures
 Approximation algorithms via
linear programming. Invited
lecture. DIMACS Workshop
on LargeScale Discrete
Optimization in Logistics,
Rutgers Univ., Feb. 1999.

—. Invited featured lecture.
Oberwolfach Workshop on
Combinatorial Optimization, Oberwolfach, Germany, Jan. 1999.
 —. Invited tutorial survey.
INFORMS (Semiannual
Meeting of the Institute for
Operations Research and
Management Science), Seattle,
Washington, Oct 1998.

—. Invited lecture. APPROX
98 (ICALP satellite), Aalborg,
Denmark, July 1998.

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

A constantfactor
approximation algorithm for the
kmedian problem. 31st Annual
ACM Symposium on Theory of
Computing (STOC 99),
Atlanta, Georgia, May 1999.

Improved approximation
algorithms for the capacitated
facility location problem. 10th
Annual ACMSIAM
Symposium on Discrete
Algorithms (SODA 99),
Baltimore, Maryland, Jan.
1999.
Publications
 A constantfactor
approximation algorithm for the
kmedian problem.
Proceedings of the 31st
Annual ACM Symposium on
Theory of Computing (May
1999), 110 (with M. Charikar,
S. Guha, and E. Tardos).
 Improved approximation
algorithms for capacitated
facility location problems.
Proceedings of the 5th Annual
ACMSIAM Symposium on
Discrete Algorithms (1999), S875S876 (with
F.A. Chudak).
 Approximation algorithms for precedenceconstrained
scheduling problems constraints
on parallel machines that run at
different speeds. Journal
Algorithms 30 (1999),
323343 (with F.A. Chudak).
 [Special issue dedicated to
invited papers from SODA 97.]
Using linear programming in the
design and analysis of
approximation algorithms: Two
illustrative problems.
Approximation Algorithms for
Combinatorial Optimization.
(K. Jansen and J. Rolim, eds.),
LNCS1444 (1998).
Recent Awards

Sonny Yau Excellence in
Teaching Prize, College of
Engineering
