David Shmoys

Key contributions

Two of his key contributions are

1. Constant factor approximation algorithm for the Generalized Assignment Problem and Unrelated Parallel Machine Scheduling.

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

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 T and write the following LP. This technique is known as parametric pruning.

L P ( T ) :: ∑ i = 1 m ∑ j = 1 n c i j x i j ≤ C ;

The obtained LP solution is then rounded to an integral solution as follows. A weighted bipartite graph G = ( W ∪ V , E ) is constructed. One side of the bipartite graph contains the job nodes, W = { w j | j ∈ J } , and the other side contains several copies of each machine node, V = { v i , s | i = 1 , 2 , . . , m ; s = 1 , 2 , . . , k i } , where k i = ⌈ ∑ j x i j ⌉ . To construct the edges to machine nodes corresponding to say machine i , first jobs are arranged in decreasing order of processing time p i j . For simplicity, suppose, p i 1 ≥ p i 2 ≥ … ≥ p i n . Now find the minimum index j 1 , such that ∑ i j 1 x i j ≥ 1 . Include in E all the edges ( w j , v i 1 , j = 1 , 2 , . . , j 1 − 1 ) with nonzero x i j and set their weights to x v i 1 j ′ = x i j . Create the edge ( w j 1 , v i 1 ) and set its weight to x v i 1 j 1 ′ = 1 − ∑ i = 1 j 1 − 1 x v i 1 j ′ . This ensures that the total weight of the edges incident on the vertex v i 1 is at most 1. If x v i 1 j 1 ′ < x i j 1 , then create an edge ( w j 1 , v i 2 ) with weight x v i 2 j 1 ′ = x i j − x v i 1 j 1 ′ . Continue with assigning edges to v i 2 in a similar way.

In the bipartite graph thus created, each job node in W has a total edge weight of 1 incident on it, and each machine node in V has edges with total weight at most 1 incident on it. Thus the vector x ′ is an instance of a fractional matching on G 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 G and using an easy charging argument, the following theorem can be proved:

Theorem: If L P ( T ) has a feasible solution then a schedule can be constructed with makespan T + m a x i , j p i , j and cost C .

Since m a x i , j p i , j ≤ T , 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 6 2 3 approximation to the metric k medians problem. This was the first paper to break the previously best known O ( log ⁡ k   log ⁡ log ⁡ k ) approximation.

Shmoys has also worked extensively on the facility location problem. His recent results include obtaining a 3 approximation algorithm for the capacitated facility location problem. The joint work with Fabian Chudak, has resulted in improving the previous known 5.69 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 ( 1 + 2 / e ) ≈ 1.736 -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[1] 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)