Skip to main content

in this section

David B. Shmoys

  • David B. Shmoys
  • Dept: Operations Research and Information Engineering
  • Title: Laibe/Acheson Professor of Business Management and Leadership
  • Address: 231 Frank H.T. Rhodes Hall
  • Phone: 607 255-9146
  • return to list


David Shmoys obtained his Ph.D. in Computer Science from the University of California at Berkeley in 1984. He has faculty appointments in both the School of Operations Research and Information Engineering and the Department of Computer Science. Shmoys' research has focused on the design and analysis of efficient algorithms for discrete optimization problems. His work has highlighted the central role that linear programming plays in the design of approximation algorithms for NP-hard problems. His current work includes the application of discrete optimization techniques to several issues in computational sustainability, as well as in the development of approximation algorithms for stochastic models of clustering, inventory, and related problems in logistics.

Research Interests

Shmoys has made fundamental contributions to the area of approximation algorithms for discrete optimization problems, having given the first constant-performance guarantees for a wide range of problems in scheduling, clustering, and supply chain management. His work on polynomial-time approximation schemes for scheduling problems introduced techniques that have subsequently been applied to a variety of other settings. His current work includes the application of discrete optimization techniques to the emerging area of computational sustainability, as well as in the development of approximation algorithms for stochastic optimization models.

Teaching Interests

Professor Shmoys teaches classes in the area of optimization, algorithm design, and the mathematical modeling of applications with an optimization component. He has developed a series of integrated weekly computational labs within the course ENGRI 1101 Engineering Applications of Operations Research, and regularly teaches a wide variety of optimization courses at all levels.

Service Interests

David Shmoys currently serves as Chair of the IEEE Technical Committee on Mathematical Foundations of Computing, and is on the Scientific Committee for the Mathematics of the Planet Earth, 2013. He is currently an Associate Editor of Mathematics of Operations Research, and an Advisory Editor for Surveys in Operations Research and Management Science, and has also been on the editorial boards of ORSA J. on Computing, Operations Research, Mathematical Programming, Discrete Applied Mathematics, Communications of the ACM, SIAM J. on Computing, and SIAM J. on Discrete Mathematics, for which he served as Editor-in-Chief. Professor Shmoys has served on numerous program and prize committees associated with SIAM, ACM, IEEE, and INFORMS.

Selected Publications

  • Williamson, David P., David B Shmoys. 2011. The Design of Approximation Algorithms. : Cambridge University Press. Cambridge University Press.
  • An, H C., Robert Kleinberg, David B Shmoys. 2012. "Improving Christofides' Algorithms for the s-t path TSP." Paper presented at Proceedings of the 44th Annual ACM Symposium on Theory of Computing
  • Shmoys, David B., Chaitanya Swamy. 2006. "An approximation scheme for stochastic linear programming and its application to stochastic integer programs." Journal of the Association for Computing Machinery 53 (6): 978-1012.
  • Hall, Leslie A., Andreas S. Schulz, David B. Shmoys, Joel Wein. 1997. "Scheduling to minimize average completion time: off-line and on-line approximation algorithms." Mathematics of Operations Research 22 (3): 513-544.
  • Carnes, T., S. Henderson, David B. Shmoys, R. MacDonald, M Aghhari. 2013. "Mathematical Programming Guides Air-Ambulance Routing at Ornge." Interfaces 43 (3): 232-239.

Selected Awards and Honors

  • Fellow (INFORMS) 2013
  • Fellow (Association for Computing Machinery (ACM)) 2002
  • Sonny Yau '72 Excellence in Teaching Award (Cornell University, College of Engineering) 2012
  • Presidential Young Investigator (National Science Foundation (NSF)) 1987
  • Phi Beta Kappa Prize (Princeton University) 1981



  • BS (Electrical Engineering and Computer Science), Princeton University, 1981
  • Ph D (Computer Science), University of California- Berkeley, 1984