Startseite > Publikationen > Publikationen


Berenbrink, Petra;Meyer auf der Heide, Friedhelm;Schröder, Klaus:

Allocating Weighted Jobs in Parallel.

SPAA 1997 : S. 302-310, Jun. 1997


It is well known that after placing m >= n balls independently and uniformly at random (i.u.r.) into n bins, the fullest bin contains Omega(log n/ log log n + (m/n)) balls, with high probability. It is also known (see [Ste96]) that a maximum load of O(m/n) can be obtained for all m >= n if a ball is allocated in one (suitably chosen) of two (i.u.r.) bins. Stemann ([Ste96]) shows that r communication rounds suffice to guarantee a maximum load of max{ r_sqrt(log n), O(m/n)}, with high probability. Adler et al. have shown in [ACMR95] that Stemanns protocol is optimal for constant r. In this paper we extend the above results in two directions: We generalize the lower bound to arbitrary r<= log log n. This implies that the result of Stemanns protocol is optimal for all r. Our main result is a generalization of Stemanns upper bound to weighted jobs: Let W^A (W^M) denote the average (maximum) weight of the balls. Further let Delta = W^A/W^M. Note that the maximum load is at least Omega(m/n*W^A + W^M). We present a protocol that achieves maximum load of y*(m/n * W^A + W^M) using O( (log log n) / (log(y*((m/n)*Delta+1))) ) rounds of communication. For uniform weights this matches the results of Stemann. In particular, for log log n rounds we achieve optimal load of O(m/n * W^A + W^M). Using this lower bound it is also shown that our algorithm is optimal in the case of weighted balls for varios degrees of uniformity.




author = {Berenbrink, Petra and Meyer auf der Heide, Friedhelm and Schr{\"o}der, Klaus},
title = {Allocating Weighted Jobs in Parallel},
journal = {SPAA 1997},
pages = {302-310},
month = jun,
year = {1997},

BibTeX in die Zwischenablage kopieren