We consider the problem of makespan minimization on unrelated machines when job sizes are stochastic. The goal is to find a fixed assignment of jobs to machines, to minimize the expected value of the maximum load over all the machines. For the identical machines special case when the size of a job is the same across all machines, a constant-factor approximation algorithm has long been known. Our main result is the first constant-factor approximation algorithm for the general case of unrelated machines. This is achieved by (i) formulating a lower bound using an exponential-size linear program that is efficiently computable, and (ii) rounding this linear program while satisfying only a specific subset of the constraints that still suffice to bound the expected makespan. We also consider two generalizations. The first is the budgeted makespan minimization problem, where the goal is to minimize the expected makespan subject to scheduling a target number (or reward) of jobs. We extend our main result to obtain a constant-factor approximation algorithm for this problem. The second problem involves @math -norm objectives, where we want to minimize the expected q-norm of the machine loads. Here we give an @math -approximation algorithm, which is a constant-factor approximation for any fixed @math .
Very recently (after the preliminary version of this paper appeared), Molinaro @cite_9 obtained an @math -approximation algorithm for the stochastic @math -norm problem for all @math , which improves over Theorem . In addition to the techniques in our paper, the main idea in @cite_9 is to use a different notion of effective size, based on the L-function method @cite_16 . We still present our algorithm analysis for Theorem as it is conceptually simpler and may provide better constant factors for small @math .
@cite_9 @cite_16
2949276956 2012362409
This paper considers stochastic optimization problems whose objective functions involve powers of random variables. For example, consider the classic Stochastic lp Load Balancing Problem (SLBp): There are @math machines and @math jobs, and known independent random variables @math decribe the load incurred on machine @math if we assign job @math to it. The goal is to assign each jobs to machines in order to minimize the expected @math -norm of the total load on the machines. While convex relaxations represent one of the most powerful algorithmic tools, in problems such as SLBp the main difficulty is to capture the objective function in a way that only depends on each random variable separately. We show how to capture @math -power-type objectives in such separable way by using the @math -function method, introduced by Lata a to relate the moment of sums of random variables to the individual marginals. We show how this quickly leads to a constant-factor approximation for very general subset selection problem with @math -moment objective. Moreover, we give a constant-factor approximation for SLBp, improving on the recent @math -approximation of [, SODA 18]. Here the application of the method is much more involved. In particular, we need to sharply connect the expected @math -norm of a random vector with the @math -moments of its marginals (machine loads), taking into account simultaneously the different scales of the loads that are incurred by an unknown assignment. For the sum S = Σ X i of a sequence (X i ) of independent symmetric (or nonnegative) random variables, we give lower and upper estimates of moments of S. The estimates are exact, up to some universal constants, and extend the previous results for particular types of variables X i .