  The configuration balancing problem with stochastic requests generalizes many
well-studied resource allocation problems such as load balancing and virtual
circuit routing. In it, we have $m$ resources and $n$ requests. Each request
has multiple possible configurations, each of which increases the load of each
resource by some amount. The goal is to select one configuration for each
request to minimize the makespan: the load of the most-loaded resource. In our
work, we focus on a stochastic setting, where we only know the distribution for
how each configuration increases the resource loads, learning the realized
value only after a configuration is chosen.
  We develop both offline and online algorithms for configuration balancing
with stochastic requests. When the requests are known offline, we give a
non-adaptive policy for configuration balancing with stochastic requests that
$O(\frac{\log m}{\log \log m})$-approximates the optimal adaptive policy. In
particular, this closes the adaptivity gap for this problem as there is an
asymptotically matching lower bound even for the very special case of load
balancing on identical machines. When requests arrive online in a list, we give
a non-adaptive policy that is $O(\log m)$ competitive. Again, this result is
asymptotically tight due to information-theoretic lower bounds for very special
cases (e.g., for load balancing on unrelated machines). Finally, we show how to
leverage adaptivity in the special case of load balancing on related machines
to obtain a constant-factor approximation offline and an $O(\log \log
m)$-approximation online. A crucial technical ingredient in all of our results
is a new structural characterization of the optimal adaptive policy that allows
us to limit the correlations between its decisions.
