Distributed Load Balancing on Unrelated Machines
Published in arXiv preprint, 2026
Authors: Aaron Bernstein, Anupam Gupta, and Zhaozi Wang
Status: Manuscript, arXiv:2607.10075
| Links: arXiv | DOI |
We give polylog-round algorithms in the CONGEST model for load balancing on unrelated machines, obtaining a $(1+\varepsilon)$-approximate fractional solution and a $(2+\varepsilon)$-approximate integral solution. The result also yields a general polylog-round $(1+\varepsilon)$-approximation for mixed packing-covering linear programs in CONGEST.