{"ID":6536310,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10075","arxiv_id":"2607.10075","title":"Distributed Load Balancing on Unrelated Machines","abstract":"We study the well-known load balancing problem in the distributed CONGEST model of computation. We consider the unrelated machines setting, where each job $j$ specifies a size $s_{ij}$ for every machine $i$. We want to find an assignment $\\varphi: J \\to M$ minimizing the maximum machine load, where the load of a machine $i$ is the total size of the jobs assigned to it. In the CONGEST model, the state-of-the-art is an algorithm that runs in polylog rounds and returns a $(1+\\varepsilon)$-approximate fractional solution from Ahmadian, Liu, Peng, and Zadimoghaddam (2021). However, this algorithm, as well as all previous CONGEST algorithms only solve a special case of load balancing, where each job has the same size on each machine. Our main contribution is an algorithm for general sizes $s_{ij}$. The algorithm computes a $(1+\\varepsilon)$-approximate fractional solution or a $(2+\\varepsilon)$-approximate integral solution in polylog rounds. The problem structure changes significantly once we allow arbitrary edge-sizes, so our techniques are very different from those used in previous algorithms for distributed load balancing. One ingredient of our result is a black-box tool of independent interest: a $(1+\\varepsilon)$-approximation algorithm to arbitrary mixed packing-covering linear programs in the CONGEST model in polylog rounds. such algorithms were known in the more powerful parallel model, but previous polylog-round algorithms in the distributed CONGEST model only solved pure packing or pure covering problems. We improve upon a recent $O(D\\,\\mathrm{polylog})$-round CONGEST algorithm for mixed packing-covering, where $D$ is the diameter of the communication graph.","short_abstract":"We study the well-known load balancing problem in the distributed CONGEST model of computation. We consider the unrelated machines setting, where each job $j$ specifies a size $s_{ij}$ for every machine $i$. We want to find an assignment $\\varphi: J \\to M$ minimizing the maximum machine load, where the load of a machin...","url_abs":"https://arxiv.org/abs/2607.10075","url_pdf":"https://arxiv.org/pdf/2607.10075v1","authors":"[\"Aaron Bernstein\",\"Anupam Gupta\",\"Zhaozi Wang\"]","published":"2026-07-11T02:05:08Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}