David Shmoys
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. 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. Key contributions. Two of his key contributions are 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 formula_1 independent jobs (denoted formula_2) have to be processed by exactly one of formula_3 unrelated parallel machines (denoted formula_4). Unrelated implies same job might take different amount of processing time on different machines. Job formula_5 takes formula_6 time units when processed by machine formula_7 and incurs a cost formula_8. Given formula_9 and formula_10, we wish to decide if there exists a schedule with total cost at most formula_9 such that for each machine formula_7 its load, the total processing time required for the jobs assigned to it  is at most formula_10. By scaling the processing times, we can assume, without loss of generality, that the machine load bounds satisfy formula_14. ``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 formula_15 ". 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 formula_15 and write the following LP. This technique is known as parametric pruning. formula_17; The obtained LP solution is then rounded to an integral solution as follows. A weighted bipartite graph formula_22 is constructed. One side of the bipartite graph contains the job nodes, formula_23, and the other side contains several copies  of each machine node, formula_24, where formula_25. To construct the edges to machine nodes corresponding to say machine formula_7, first jobs are arranged in decreasing order of processing time formula_27. For simplicity, suppose, formula_28. Now find the minimum index formula_29, such that formula_30. Include in formula_31 all the edges formula_32 with nonzero formula_33 and set their weights to formula_34. Create the edge formula_35 and set its weight to formula_36. This ensures that the total weight of the edges incident on the vertex formula_37 is at most 1. If formula_38, then create an edge formula_39 with weight formula_40. Continue with assigning  edges to formula_41 in a similar way. In the bipartite graph thus created, each job node in formula_42 has a total edge weight of 1 incident on it, and each machine node in formula_43 has edges with total weight at most 1 incident on it. Thus the vector formula_44 is an instance of a fractional matching on formula_45 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 formula_45 and using an easy charging argument, the following theorem can  be proved: Theorem: If formula_47 has a feasible solution then a schedule can be constructed with makespan formula_48 and cost formula_9. Since formula_50, a 2 approximation is obtained. 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 formula_51 approximation to the metric k medians problem. This was the first paper to break the previously best known formula_52 approximation. Shmoys has also worked extensively on the facility location problem. His recent results include obtaining a formula_53 approximation algorithm for the capacitated facility location problem. The  joint work with Fabian Chudak, has resulted in improving the previous known formula_54 approximation for the same problem. 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 uncapacitated version of the facility location problem, again in a joint work with Chudak he obtained a formula_55-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. 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)