Close
David Shmoys

David B. Shmoys

Acheson/Laibe Professor of Business Management and Leadership Studies
Operations Research and Information Engineering
Frank H T Rhodes Hall, Room 231

Biography

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. In particular, his most recent area of interest has been in the development of algorithm tools to design and support bike-sharing systems.

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.

Selected Publications

  • Williamson, David P., David B Shmoys.  2011. The Design of Approximation Algorithms.  : Cambridge University Press. United Kingdom:Cambridge University Press.
  • An, H C., R. Kleinberg, D B Shmoys.  2015. "Improving Christofides' Algorithm for the s-t Path TSP."  Journal of the ACM 62 (5): 1-28.
  • 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

Education

University of California- Berkeley 1984

Websites

In the News