arXiv preprint ·
Dynamic Load Balancing under Restricting Updates
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the problem of load balancing in the dynamic setting. The input is a bipartite graph $G = (J \cup M, E)$ of jobs $J$ and machines $M$. Every job has a positive weight $w(j)$. The goal is to assign every job in $J$ to an adjacent machine in $M$ so as to minimize the maximum machine load, where the load of a machine is the sum of the weights of the jobs assigned to it. Although load balancing has been studied extensively in many models of computation, the only previous result in the dynamic model addresses the \emph{incremental} setting, where updates take the form of edge insertions and job deletions [BKS23b]. The authors show a $(1+ε)$-approximation for incremental \emph{fractional} load balancing with $\text{poly}(\log(n),1/ε)$ update time; they point out that their techniques do not extend to the decremental setting. Main Result: We obtain an algorithm which maintains a $(1+ε)$-approximate solution to the fractional load balancing problem under edge deletions and job insertions in $\tilde{O}(\log (n), 1/ε)$ update time. Our techniques are very different from those of the incremental algorithm of [BKS23b]. Instead, our algorithm is inspired by a load-balancing algorithm from the {\sc congest} model of computation [ALPZ21]. We develop a novel analytic framework for this algorithm, which allows us to show that it performs well in the dynamic setting. Rounding Scheme: We also present a black-box rounding scheme for dynamic load balancing. Plugging in our fractional algorithm, we obtain a decremental algorithm for $(2+ε)$-approximate \emph{integral} load balancing with $\text{poly}(\log(n),1/ε)$ update time. We also obtain the same bounds for incremental load balancing by plugging in the fractional algorithm of [BKS23b].
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Competitive Online Clustering with Movement Cost
Near-Linear Time Maximum Clique in Circular Arc Graphs
On the Metric Distortion of the Minimum Spanning Tree Problem
Computing faster with a full memory: Catalytic algorithms break time-space lower bounds
Online geometric matching and segments block points
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.