Stochastic Load Balancing on Unrelated Machines

We consider the problem of makespan minimization when job sizes are stochastic. The goal is to find a fixed assignment of jobs to machines so as to minimize the expected makespan. In the special case of identical machines, a constant-factor approximation algorithm has long been known, but the problem remained open even for the next-harder related machines case. We obtain the first constant-factor approximation in the setting of general unrelated machines. We also obtain algorithms for two generalizations (i) a constant-factor approximation for the ``budgeted'' makespan problem, and (ii) an O(q / log q)-approximation for q-norm minimization.

This is joint work with Anupam Gupta, Amit Kumar and Xiangkun Shen.