The design and analysis of algorithms for discrete optimization problems forms the primary research output of David Shmoys, a computer scientist and mathematician currently based at Cornell University in Ithaca. His work frequently utilizes linear programming to establish constant factor performance guarantees for complex tasks such as the generalized assignment problem and various scheduling challenges.
Academic Background
Born in 1959, Shmoys pursued his formal education in the United States. He attended Princeton University for undergraduate studies before moving to the University of California, Berkeley. He completed his doctoral degree at Berkeley in 1984. Throughout his career, he has focused on the intersection of mathematical theory and computer science, maintaining a long-standing academic appointment within the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →Contributions to Discrete Optimization
Shmoys is noted for developing polynomial-time approximation schemes for scheduling problems. His methodology often involves parametric pruning and the rounding of extreme point solutions derived from linear programming. Key areas of his research include the k-center and k-median problems, as well as the generalized assignment problem. These efforts have provided foundational performance benchmarks that are applied in numerous subsequent computational studies.
Contemporary Research and Professional Standing
Beyond his classical work in algorithm design, his recent research interests include stochastic optimization for data-driven models. These modern applications span diverse fields such as transportation systems, IoT network design, congressional districting, and COVID epidemiological modeling. His contributions have been formally recognized by his peers; he is an ACM Fellow, a Fellow of the Society for Industrial and Applied Mathematics, and a recipient of the 2013 Frederick W. Lanchester Prize.
Fast facts
- Born: 1959
- Citizenship: United States
- Ph.D. Institution: University of California, Berkeley
- Primary Employer: Cornell University
- ACM Fellow: 2001
- SIAM Fellow: 2012
- Frederick W. Lanchester Prize: 2013
Questions readers ask
What is the primary focus of David Shmoys's research?
His work centers on the design and analysis of algorithms for discrete optimization problems, particularly those involving scheduling and clustering.
What are some practical applications of his algorithmic research?
His work has been applied to diverse areas such as transportation systems, IoT network design, congressional districting, and epidemiological modeling.
Achievements
- Frederick W. Lanchester Prize — 2013
- Held posts at Cornell University
