David B Shmoys
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.
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.
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.
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.
- 2011. The Design of Approximation Algorithms. : Cambridge University Press. Cambridge University Press. .
- 2015. "Improving Christofides' Algorithm for the s-t Path TSP." Journal of the ACM 62 (5): 1-28. .
- 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. .
- 1997. "Scheduling to minimize average completion time: off-line and on-line approximation algorithms." Mathematics of Operations Research 22 (3): 513-544. .
- 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