Skip to main content

Research Repository

Advanced Search

Randomized diffusion for indivisible loads

Berenbrink, Petra; Cooper, Colin; Friedetzky, Tom; Friedrich, Tobias; Sauerwald, Thomas

Randomized diffusion for indivisible loads Thumbnail


Authors

Petra Berenbrink

Colin Cooper

Tobias Friedrich

Thomas Sauerwald



Abstract

We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constant-degree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds. For hypercubes we obtain a polynomial improvement.

Citation

Berenbrink, P., Cooper, C., Friedetzky, T., Friedrich, T., & Sauerwald, T. (2015). Randomized diffusion for indivisible loads. Journal of Computer and System Sciences, 81(1), 159-185. https://doi.org/10.1016/j.jcss.2014.04.027

Journal Article Type Article
Acceptance Date Apr 17, 2014
Publication Date Feb 1, 2015
Deposit Date Dec 16, 2015
Publicly Available Date Mar 14, 2016
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 81
Issue 1
Pages 159-185
DOI https://doi.org/10.1016/j.jcss.2014.04.027

Files





You might also like



Downloadable Citations