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.
His major focus has been in the design and analysis of algorithms for discrete optimization problems.
In particular, his work has highlighted the role of linear programming in the design of approximation algorithms for NP-hard problems.
Polynomial-time approximation schemes that he developed for scheduling problems have found applications in many subsequent works.
His current research includes stochastic optimization for data-driven models in a broad cross-section of areas, including COVID epidemiological modeling, congressional districting, transportation, and IoT network design.
Shmoys is married to Éva Tardos, who is the Jacob Gould Schurman Professor of Computer Science at Cornell University.
Unrelated implies same job might take different amount of processing time on different machines.
, we wish to decide if there exists a schedule with total cost at most
its load, the total processing time required for the jobs assigned to it is at most
By scaling the processing times, we can assume, without loss of generality, that the machine load bounds satisfy
``In other words, generalized assignment problem is to find a schedule of minimum cost subject to the constraint that the makespan, that the maximum machine load is at most
The work of Shmoys with Lenstra and Tardos cited here[2] 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.
, first jobs are arranged in decreasing order of processing time
This ensures that the total weight of the edges incident on the vertex
has a total edge weight of 1 incident on it, and each machine node in
and thus it can be rounded to obtain an integral matching of same cost.
Now considering the ordering of processing times of the jobs on the machines nodes during construction of
has a feasible solution then a schedule can be constructed with makespan
The paper[3] is a joint work by Moses Charikar, Sudipto Guha, Éva Tardos and David Shmoys.
Shmoys has also worked extensively on the facility location problem.
approximation algorithm for the capacitated facility location problem.
The joint work with Fabian Chudak,[4] has resulted in improving the previous known
Their algorithm is based on a variant of randomized rounding called the randomized rounding with a backup, since a backup solution is incorporated to correct for the fact that the ordinary randomized rounding rarely generates a feasible solution to the associated set covering problem.
For the incapacitated version of the facility location problem, again in a joint work with Chudak[5] he obtained a
-approximation algorithm which was a significant improvement on the previously known approximation guarantees.
The improved algorithm works by rounding an optimal fractional solution of a linear programming relaxation and using the properties of the optimal solutions of the linear program and a generalization of a decomposition technique.
He has received the Sonny Yau Excellence in Teaching Award three times from Cornell's College of Engineering, and has been awarded a NSF Presidential Young Investigator Award, the Frederick W. Lanchester Prize (2013), the Daniel H. Wagner Prize for Excellence in the Practice of Advanced Analytics and Operations Research (2018), and the Khachiyan Prize of the INFORMS Optimization Society (2022), which is awarded annually for life-time achievements in the area of optimization.