Stochastic ep load balancing and moment problems via the L-function method

Marco Molinaro

Abstract

This paper addresses stochastic optimization problems where objective functions involve powers of random variables, specifically focusing on the Stochastic $\ell_p$ Load Balancing Problem (StochLoadBalp). In this setting, $n$ jobs must be assigned to $m$ machines, where job sizes are independent random variables $Y_{ij}$. The goal is to minimize the expected $\ell_p$-norm of the resulting machine loads. Historically, capturing such objectives in a separable way—essential for convex relaxation—has been a major hurdle, with previous best approximations scaling at $O(p / \ln p)$. This work introduces the L-function method to this domain, achieving the first constant-factor approximation for StochLoadBalp and general subset selection problems with $p$-moment objectives.

Introduction

In the classic load balancing problem, the objective is to assign jobs to machines to minimize a measure of congestion. In the stochastic variant, the size of job $j$ on machine $i$ is a random variable $Y_{ij}$, and the assignment must be determined before the actual realizations of these variables are known.

The objective is to minimize the expected $\ell_p$-norm of the loads: $$\mathbb{E}\left[ \left( \sum_{i=1}^m \left( \sum_{j \in J_i} Y_{ij} \right)^p \right)^{1/p} \right]$$

As $p$ varies, this objective interpolates between minimizing the total expected load ($p=1$) and the expected makespan ($p=\infty$). The primary difficulty lies in the non-separability of the expectation of a norm of sums. Standard optimization tools like Linear Programming (LP) struggle because the contribution of a single job to the objective depends non-linearly on all other jobs assigned to the same machine.

The L-function Method and Separability

The core innovation of this paper is the application of the L-function method, originally developed by Rafał Latała to characterize the moments of sums of independent random variables.

The method utilizes a proxy for the "size" of a random variable $X$, denoted as $\nu_{\epsilon, p}(X)$. Latała's fundamental insight was that the $p$-moment of a sum of independent variables is approximately $\epsilon$ if and only if the sum of the individual $\nu$ values is approximately 1. This effectively "linearizes" the moment of a sum, transforming a complex stochastic moment into a separable sum of individual marginals.

Algorithmic Framework

To solve the StochLoadBalp, the author develops a multi-stage algorithmic pipeline:

  1. Convex Relaxation: The paper constructs a massive Linear Program with exponentially many constraints based on the $\nu$ proxies. This LP captures the $p$-moment requirements for each machine.
  2. Structural Multi-scale Analysis: A significant technical contribution is Theorem 5, which relates the expected $\ell_p$-norm of a random vector to the $p$-moments of its coordinate-marginals (the machine loads). This requires a "multi-scale" approach to ensure the approximation holds even when machines operate at vastly different load scales.
  3. LP Reduction and Rounding: Because the initial LP is not conducive to integral rounding, the author uses its solution to derive a "Reduced LP." This reduced version resembles a Generalized Assignment Problem (GAP), which can then be solved using the Shmoys-Tardos rounding algorithm to produce a discrete job assignment.

Key Results

Constant-Factor Approximation

The paper proves that the Stochastic $\ell_p$ Load Balancing problem admits a constant-factor approximation for all $p \in [1, \infty]$. This is a major improvement over the previous state-of-the-art $O(p / \ln p)$ bound, which diverged as $p$ increased.

General Subset Selection

Beyond load balancing, the L-function method is shown to provide constant-factor approximations for a general class of subset selection problems. In these problems, the goal is to select a subset of items to maximize or minimize the $p$-moment of their sum, subject to various combinatorial constraints.

Discussion and Limitations

While the result is a theoretical breakthrough, there are practical considerations for implementation. The constants involved in the approximation (e.g., values like 10 or 44 appearing in specific lemmas) are relatively large, which is common in first-of-their-kind constant-factor proofs.

Furthermore, the method relies on the independence of the random variables $Y_{ij}$. If job sizes were correlated—for instance, if a specific machine failure affected all jobs assigned to it—the current L-function formulation would not directly apply. Finally, the paper focuses on non-adaptive assignments. Future research may explore whether these "linearization" techniques can be extended to adaptive settings where assignments can be modified as job sizes are revealed.

Conclusion

By leveraging the L-function method, this work demonstrates that complex, non-separable stochastic objectives can be managed through carefully constructed linear relaxations. The transition from $O(p / \ln p)$ to a constant-factor approximation represents a significant step forward in the field of stochastic load balancing.

Summary updated

Abstract

This paper considers stochastic optimization problems whose objective functions involve powers of random variables. For a concrete example, consider the classic Stochasticep Load Balancing Problem (StochLoadBalp): There are m machines and n jobs, and we are given independent random variables Yij 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 ep-norm of the total load incurred over the machines. That is, letting Ji denote the jobs assigned to machine i, we want to minimize E(∑i(∑j ∈ JiYij)p)1 / p. While convex relaxations represent one of the most powerful algorithmic tools, in problems such as StochLoadBalp 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 StochLoadBalp, 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 ep-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.
BibTeX
@misc{molinaro2019stochastic,
  author = {Marco Molinaro},
  title = {{Stochastic ep load balancing and moment problems via the L-function method}},
  year = {2019},
  eprint = {1810.05245},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.05245},
}
Figure