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 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 optimumis 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 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
-
Editor-in-Chief: SIAM Journal
Discrete Mathematics
- Editor: SIAM Journal
Computing
- Associate Editor: Mathematics
of Operations Research, Mathematical Programming,
Journal Scheduling
- Program Committee Chair: 11thACM-SIAM 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)
- Co-Organizer: Fields Institute
Workshop on Approximation
Algorithms
-
Council Member: Mathematical
Programming Society
Lectures
- Approximation algorithms via
linear programming. Invited
lecture. DIMACS Workshop
on Large-Scale Discrete
Optimization in Logistics,
Rutgers Univ., Feb. 1999.
-
—. Invited featured lecture.
Oberwolfach Workshop on
Combinatorial Optimization, Oberwolfach, Germany, Jan. 1999.
- —. Invited tutorial survey.
INFORMS (Semi-annual
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 constant-factor
approximation algorithm for the
k-median 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 ACM-SIAM
Symposium on Discrete
Algorithms (SODA 99),
Baltimore, Maryland, Jan.
1999.
Publications
- A constant-factor
approximation algorithm for the
k-median problem.
Proceedings of the 31st
Annual ACM Symposium on
Theory of Computing (May
1999), 1-10 (with M. Charikar,
S. Guha, and E. Tardos).
- Improved approximation
algorithms for capacitated
facility location problems.
Proceedings of the 5th Annual
ACM-SIAM Symposium on
Discrete Algorithms (1999), S875-S876 (with
F.A. Chudak).
- Approximation algorithms for precedence-constrained
scheduling problems constraints
on parallel machines that run at
different speeds. Journal
Algorithms 30 (1999),
323-343 (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
|
