Stochastic ℓp Load Balancing and Moment Problems via the L-Function Method

This paper considers stochastic optimization problems whose objective functions involve powers of random variables. For a concrete example, consider the classic Stochastic ℓ_p Load Balancing Problem (StochLoadBal_p): There are m machines and n jobs, and we are given independent random variables Y_ij describing the distribution of the load incurred on machine i if we assign job j to it. The goal is to assign each job to the machines in order to minimize the expected ℓ_p-norm of the total load incurred over the machines. That is, letting J_i denote the jobs assigned to machine i, we want to minimize \(\mathbb{E}(\sum_i(\sum_{j{\epsilon}J_i}Y_{ij})^p)^{1/p}\). While convex relaxations represent one of the most powerful algorithmic tools, in problems such as StochLoadBal_p the main difficulty is to capture such objective function in a way that only depends on each random variable separately.

In this paper, show how to capture p-power-type objectives in such separable way by using the L-function method. This method was precisely introduced by Latala to capture in a sharp way the moment of sums of random variables through the individual marginals. We first show how this quickly leads to a constant-factor approximation for very general subset selection problem with p-moment objective.

Moreover, we give a constant-factor approximation for StochLoadBal_p, improving on the recent O(p/ ln p)-approximation of [Gupta et al., SODA 18]. Here the application of the method is much more involved. In particular, we need to prove structural results connecting the expected ℓ_p-norm of a random vector with the p-moments of its coordinate-marginals (machine loads) in a sharp way, taking into account simultaneously the different scales of the loads that are incurred in the different machines by an unknown assignment. Moreover, our starting convex (indeed linear) relaxation has exponentially many constraints that are not conducive to integral rounding; we need to use the solution of this LP to obtain a reduced LP which can then be used to obtain the desired assignment.