Smoothed analysis of balancing networks

DOI10.1002/rsa.20341zbMath1223.68019arXiv1006.1443OpenAlexW2571496458MaRDI QIDQ5198673

Thomas Sauerwald, Tobias Friedrich, Dan Vilenchik

Publication date: 9 August 2011

Published in: Random Structures & Algorithms, Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1006.1443

zbMATH Keywords

load balancingdistributed computingaverage case analysissmoothed analysisbalancing networks

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Mathematical problems of computer architecture (68M07) Distributed systems (68M14)

Related Items (3)

Scheduling networks with variable topology in the presence of noise and delays in measurements ⋮ Smoothed Analysis of Local Search Algorithms ⋮ Approximate consensus in the dynamic stochastic network with incomplete information and measurement delays

Cites Work

• Smoothed analysis of integer programming
• Smoothed analysis of binary search trees
• Self-stabilizing smoothing and balancing networks
• Randomized smoothing networks
• On smoothed analysis in dense graphs and formulas
• The periodic balanced sorting network
• Smoothed analysis of algorithms
• Counting networks
• How many random edges make a dense graph hamiltonian?
• Near-perfect load balancing by randomized rounding
• The diameter of randomly perturbed digraphs and some applications

This page was built for publication: Smoothed analysis of balancing networks