David Shmoys

David B. Shmoys

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

Biography

David Shmoys is the Laibe/Acheson Professor and Director of the Center for Data Science for Enterprise & Society at Cornell University. He obtained his Ph.D. in computer science from the University of California at Berkeley in 1984, and held postdoctoral positions at MSRI in Berkeley and Harvard University, and a faculty position at MIT before joining the faculty at Cornell University. He was Chair of the Cornell Provost’s “Radical Collaborations” Task Force on Data Science and was co-Chair of the Academic Planning Committee for Cornell Tech. His research has focused on the design and analysis of efficient algorithms for discrete optimization problems, with applications including scheduling, inventory theory, computational biology, computational sustainability, and most recently, data-driven decision-making in the sharing economy. His work has highlighted the central role that linear programming plays in the design of approximation algorithms for NP-hard problems. His book (co-authored with David Williamson), The Design of Approximation Algorithms, was awarded the 2013 INFORMS Lanchester Prize and his work on bike-sharing (joint with Daniel Freund, Shane Henderson, and Eoin O’Mahony) was awarded the 2018 INFORMS Wagner Prize. David is a Fellow of the ACM, INFORMS, and SIAM, and was an NSF Presidential Young Investigator.

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.

Service Interests

David Shmoys served as Past-Chair of the IEEE Technical Committee on Mathematical Foundations of Computing, is on the Board of Governors of The Institute for Mathematics and Applications (IMA) and the Advisory Board of the SIAM Activity Group on the Mathematics of the Planet Earth. He is currently Editor-in-Chief (for Theoretical Computer Science) of Research in the Mathematical Sciences, 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. 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 & 2021
  • Presidential Young Investigator (National Science Foundation (NSF)) 1987
  • Phi Beta Kappa Prize (Princeton University) 1981

Education

  • B.S. (Electrical Engineering and Computer Science), Princeton University, 1981
  • Ph.D. (Computer Science), University of California, Berkeley, 1984

Websites

In the News