Abstract. Load balancing is a well-studied problem, with balls-in-bins being the primary framework. The greedy algorithm [Formula: see text] of Azar et al. [ SIAM J. Comput., 29 (1999), pp. 180–200] places each ball by probing [Formula: see text] random bins and placing the ball in the least loaded of them. With high probability, the maximum load under [Formula: see text] is exponentially lower than the result when balls are placed uniformly randomly. Vöcking [ J. ACM, 50 (2003), pp. 568–589] showed that a slightly asymmetric variant, [Formula: see text], provides a further significant improvement. However, this improvement comes at the additional computational cost of imposing structure on the bins. Here, we present a fully decentralized and easy-to-implement algorithm called [Formula: see text] that combines the simplicity of [Formula: see text] and the improved balance of [Formula: see text]. The key idea in [Formula: see text] is to probe until a different bin size from the first observation is located and then place the ball. Although the number of probes could be quite large for some of the balls, we show that [Formula: see text] requires only at most [Formula: see text] probes on average per ball (in both the standard and the heavily loaded settings). Thus the number of probes is no greater than that of either [Formula: see text] or [Formula: see text]. More importantly, we show that [Formula: see text] closely matches the improved maximum load ensured by [Formula: see text] in both the standard and heavily loaded settings. We further provide a tight lower bound on the maximum load up to [Formula: see text] terms. We additionally give experimental data that [Formula: see text] is indeed as good as [Formula: see text], if not better, in practice.

The well-studied “power of two choices” family of algorithms creates balanced allocations of $m$ balls into $n$ bins by, for each ball, selecting a few bins at random and then placing the item in the least-loaded bin. A natural variation is to create an unbalanced allocation by, for each ball, selecting a few bins at random and then placing the ball in the most-loaded bin. Surprisingly, this variation has not been previously studied. This paper introduces this family of unbalanced allocation processes and begins its analysis. The behavior of the bounded $m$ case is analyzed in detail via differential equations and coupling, and some preliminary results for the general case are presented.

Load balancing is a well-studied problem, with balls-inbins being the primary framework. The greedy algorithm Greedy[d] of Azar et al. places each ball by probing d > 1 random bins and placing the ball in the least loaded of them. It ensures a maximum load that is exponentially better than the strategy of placing each ball uniformly at random. Vöcking showed that a slightly asymmetric variant, Left[d], provides a further significant improvement. However, this improvement comes at an additional computational cost of imposing structure on the bins. Here, we present a fully decentralized and easy-to-implement algorithm called FirstDiff[d] that combines the simplicity of Greedy[d] and the improved balance of Left[d]. The key idea in FirstDiff[d] is to probe until a different bin size from the first observation is located, then place the ball. Although the number of probes could be quite large for some of the balls, we show that FirstDiff[d] requires only d probes on average per ball (in both the standard and the heavily-loaded settings). Thus the number of probes is no greater than either that of Greedy[d] or Left[d]. More importantly, we show that FirstDiff[d] closely matches the improved maximum load ensured by Left[d] in both the standard and heavily-loaded settings. We additionally give experimental data that FirstDiff[d] is indeed as good as Left[d], if not better, in practice.

For a rooted graph G, let $EV(G;p)$ be the expected number of vertices reachable from the root when each edge has an independent probability p of operating successfully. We examine combinatorial properties of this polynomial, proving that G is k-edge connected if and only if $EV'(G;1)=\cdots=EV^{k-1}(G;1)=0$. We find bounds on the first and second derivatives of $EV(G;p)$; applications yield characterizations of rooted paths and cycles in terms of the polynomial. We prove reconstruction results for rooted trees and a negative result concerning reconstruction of more complicated rooted graphs. We also prove that the norm of the largest root of $EV(G;p)$ in $\mathbb{Q}[i]$ gives a sharp lower bound on the number of vertices of G.