1998 - 1999 CS Annual Report                                                                  Faculty
choices.gif (4488 bytes)

David B. Shmoys


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
  • 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 
  • 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. 
  • 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