David Shmoys

David Shmoys
David Shmoys
Born	1959 (age 57–58)
Fields	Computer Science, Computational complexity theory
Institutions	Cornell
Alma mater	Princeton, University of California, Berkeley
Thesis	Approximation Algorithms for Problems in Sequencing, Scheduling, and Communication Network Design (1984)
Doctoral advisor	Eugene Lawler
Notable awards	Frederick W. Lanchester Prize (2013)
Website people.orie.cornell.edu/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.

Two of his key contributions are

These contributions are described briefly below:

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 ${\displaystyle n}$ independent jobs (denoted ${\displaystyle J}$) have to be processed by exactly one of ${\displaystyle m}$ unrelated parallel machines (denoted ${\displaystyle M}$). Unrelated implies same job might take different amount of processing time on different machines. Job ${\displaystyle j}$ takes ${\displaystyle p_{i,j}}$ time units when processed by machine ${\displaystyle i}$ and incurs a cost ${\displaystyle c_{i,j},i=1,2,..,m;j=1,2,..,n;n\geq m}$. Given ${\displaystyle C}$ and ${\displaystyle T_{i},i=1,2,..,m}$, we wish to decide if there exists a schedule with total cost at most ${\displaystyle C}$ such that for each machine ${\displaystyle i}$ its load, the total processing time required for the jobs assigned to it is at most ${\displaystyle T_{i},i=1,2,..,m}$. By scaling the processing times, we can assume, without loss of generality, that the machine load bounds satisfy ${\displaystyle T_{1}=T_{2}=..=T_{m}=T}$. ``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 ${\displaystyle T}$ ".

...
Wikipedia