Name David Shmoys
|Doctoral advisor Eugene Lawler|
|Alma mater Princeton,
University of California, Berkeley|
Thesis Approximation Algorithms for Problems in Sequencing, Scheduling, and Communication Network Design (1984)
Notable awards Frederick W. Lanchester Prize (2013)
Books The Design of Approximation Algorithms
Education University of California, Berkeley, Princeton University
Fields Computer Science, Computational complexity theory
David Bernard Shmoys (born 1959) is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems.
- Key contributions
- Generalized Assignment Problem Unrelated Parallel Machine Scheduling
- K medians and Facility Location Problem
- Awards honors
In particular, his work has highlighted the role of linear programming in the design of approximation algorithms for NP-hard problems. He is known for his pioneering research on providing first constant factor performance guarantee for several scheduling and clustering problems including the k-center and k-median problems and the generalized assignment problem. Polynomial-time approximation schemes that he developed for scheduling problems have found applications in many subsequent works. His current research includes stochastic optimization, computational sustainability and optimization techniques in computational biology. Shmoys is married to Éva Tardos, who is the Jacob Gould Schurman Professor of Computer Science at Cornell University.
Two of his key contributions are
- Constant factor approximation algorithm for the Generalized Assignment Problem and Unrelated Parallel Machine Scheduling.
- Constant factor approximation algorithm for k-Medians and Facility location problem.
These contributions are described briefly below:
Generalized Assignment Problem & Unrelated Parallel Machine Scheduling
The paper is a joint work by David Shmoys and Eva Tardos.
The generalized assignment problem can be viewed as the following problem of scheduling unrelated parallel machine with costs. Each of
The work of Shmoys with Lenstra and Tardos cited here gives a 2 approximation algorithm for the unit cost case. The algorithm is based on a clever design of linear program using parametric pruning and then rounding an extreme point solution of the linear program deterministically. Algorithm for the generalized assignment problem is based on a similar LP through parametric pruning and then using a new rounding technique on a carefully designed bipartite graph. We now state the LP formulation and briefly describe the rounding technique.
We guess the optimum value of makespan
The obtained LP solution is then rounded to an integral solution as follows. A weighted bipartite graph
In the bipartite graph thus created, each job node in
Now considering the ordering of processing times of the jobs on the machines nodes during construction of
K-medians and Facility Location Problem
The paper is a joint work by Moses Charikar, Sudipto Guha, Éva Tardos and David Shmoys. They obtain a
Shmoys has also worked extensively on the facility location problem. His recent results include obtaining a
For the uncapacitated version of the facility location problem, again in a joint work with Chudak he obtained a
Awards & honors
David Shmoys is an ACM Fellow and a Fellow of the Institute for Operations Research and the Management Sciences (INFORMS) (2013). He received College of Engineering Sonny Yau Excellence in Teaching Award three times and has been awarded NSF Presidential Young Investigator Award and the Frederick W. Lanchester Prize (2013)