Stochastic Makespan Minimization in Structured Set Systems

Abstract

We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of n tasks and m resources, where each task j uses some subset of the resources. Tasks have random sizes X_j, and our goal is to non-adaptively select t tasks to minimize the expected maximum load over all resources, where the load on any resource i is the total size of all selected tasks that use i. For example, given a set of intervals in time, with each interval j having random load X_j, how do we choose t intervals to minimize the expected maximum load at any time? Our technique is also applicable to other problems with some geometric structure in the relation between tasks and resources; e.g., packing paths, rectangles, and "fat" objects. Specifically, we give an O(\log\log m)-approximation algorithm for all these problems. Our approach uses a strong LP relaxation using the cumulant generating functions of the random variables. We also show that this LP has an Ω(\log^* m) integrality gap even for the problem of selecting intervals on a line. Moreover, we show logarithmic gaps for problems without geometric structure, showing that some structure is needed to get good results using these techniques.