  A cloud scheduler packs tasks onto machines with contradictory goals of (1)
using the machines as efficiently as possible while (2) avoiding overloading
that might result in CPU throttling or out-of-memory errors. We take a
stochastic approach that models the uncertainty of tasks' resource requirements
by random variables. We focus on a little-explored case of items, each having a
Bernoulli distribution that corresponds to tasks that are either idle or need a
certain CPU share. RPAP, our online approximation algorithm, upper-bounds a
subset of items by Poisson distributions. Unlike existing algorithms for
Bernoulli items that prove the approximation ratio only up to a multiplicative
constant, we provide a closed-form expression. We derive RPAPC, a combined
approach having the same theoretical guarantees as RPAP. In simulations,
RPAPC's results are close to FFR, a greedy heuristic with no worst-case
guarantees; RPAPC slightly outperforms FFR on datasets with small items.
