Randomized diffusion for indivisible loads

DOI10.1016/j.jcss.2014.04.027zbMath1410.68028OpenAlexW2075553387MaRDI QIDQ743119

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

Publication date: 22 September 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.04.027

zbMATH Keywords

diffusionrandom walkload balancingdistributed computingrandomized algorithms

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Beyond good partition shapes: an analysis of diffusive graph partitioning, Discrete load balancing on complete bipartite graphs, Does adding more agents make a difference? A case study of cover time for the rotor-router

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First- and second-order diffusive methods for rapid, coarse, distributed load balancing
• Quasirandom Load Balancing
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• Simulating a Random Walk with Constant Error
• Deterministic Random Walks on the Two-Dimensional Grid
• Random Walk: A Modern Introduction
• Tight Analyses of Two Local Load Balancing Algorithms
• Bipartite Subgraphs and the Smallest Eigenvalue
• Near-perfect load balancing by randomized rounding
• Discrete load balancing is (almost) as easy as continuous load balancing
• Distributing Unit Size Workload Packages in Heterogeneous Networks
• Analyzing Disturbed Diffusion on Networks
• Efficient schemes for nearest neighbor load balancing
• Concentration of Measure for the Analysis of Randomized Algorithms