PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Load Balancing under Restricting Updates

Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak

arXiv:2610.23768v1cs.DS

TL;DR

Dynamic load balancing assigns weighted jobs to adjacent machines while minimizing the maximum load, but prior dynamic results covered only the incremental setting. This paper adapts a CONGEST-inspired algorithm to decremental fractional load balancing and adds a rounding scheme, obtaining approximation guarantees for partially dynamic fractional and integral assignments.

  • Problem

    Dynamic load balancing minimizes the maximum machine load, but the only known dynamic result covers incremental fractional assignments, and its techniques do not extend to decremental updates [BKS23b].

    Source: §1 · p. 3

  • Method

    The algorithm starts from a CONGEST multiplicative-update method and uses a history graph to record job and machine levels and relevant algorithm events.

    Source: §2.1 · pp. 5–6

  • Results

    (1 + ϵ) approximation: fractional assignments under edge deletions and job insertions take total update time O(m poly(log(nW)/ϵ)); randomized integral assignments achieve a (2 + ϵ)-approximation.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The rounding scheme yields a decremental integral approximation whose ratio matches, up to a (1+ϵ) factor, the best-known polynomial-time static algorithms [LST90, ST93].

    Source: §1 · p. 3, §1.1 · p. 4

    The results are partially dynamic; extending the (1 + ϵ)-approximation to fully dynamic load balancing is out of reach while similarly strong fully dynamic matching remains unresolved.

    Source: §1 · p. 3, §1.2 · p. 4

Abstract

from arXiv · show

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+\epsilon)$-approximation for incremental \emph{fractional} load balancing with $\text{poly}(\log(n),1/\epsilon)$ 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+\epsilon)$-approximate solution to the fractional load balancing problem under edge deletions and job insertions in $\tilde{O}(\log (n), 1/\epsilon)$ 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+\epsilon)$-approximate \emph{integral} load balancing with $\text{poly}(\log(n),1/\epsilon)$ update time. We also obtain the same bounds for incremental load balancing by plugging in the fractional algorithm of [BKS23b].

1 Introduction

The paper addresses dynamic load balancing, where the goal is to assign weighted jobs to adjacent machines while minimizing the maximum machine load. It extends efficient fractional load balancing to decremental updates and uses rounding to obtain integral guarantees, while explaining why fully dynamic near-optimal algorithms remain out of reach.

1 Introduction

  • The prior dynamic result maintained a (1 + ϵ)-approximate fractional assignment only for incremental updates, and its authors note that their techniques do not extend to decremental updates [BKS23b].The paper characterizes its decremental fractional result as obtaining the same bounds.Source: §1 · p. 3

1.1 Our Contributions

  • A (1 + ϵ)-approximate fractional assignment is maintained under edge deletions and job insertions in total update time O(m poly(log(nW)/ϵ)).Here m is the total number of edges ever present, n the final number of nodes, and job weights lie in [1, W].Source: §1.1 · p. 3
  • A randomized decremental algorithm maintains an integral assignment with maximum load at most (1 + ϵ) · Opt + W ≤ (2 + ϵ) · Opt, in total update time O(m poly(log(nW)/ϵ)) with high probability.The algorithm works against an adaptive adversary.Source: §1.1 · pp. 3–4
  • The black-box rounding scheme also yields the same bounds for incremental integral load balancing when applied to [BKS23b], giving the first efficient algorithm for that setting.The rounding scheme modifies an earlier scheme for online algorithms to ensure efficient update time.Source: §1.1 · pp. 3–4

1.2 Related Work: Maximum Flow and Maximum Matching

  • A fully dynamic (1 + ϵ)-approximation for fractional load balancing would imply the same bounds for fully dynamic integral matching, a problem described as a major open challenge.The authors therefore identify fully dynamic near-optimal load balancing as out of reach until the simpler matching problem is better understood.Source: §1.2 · p. 4
  • Efficient fully dynamic load balancing remains open even with weaker approximation: a 2−Ω(1)-approximation has a conditional large-update-time lower bound for unweighted graphs, while bounds better than 2 remain unknown.The paper leaves open whether efficient O(1)- or polylog-approximation algorithms exist.Source: §1.2 · p. 4

2 Overview

The overview describes a dynamic fractional-assignment algorithm and a black-box rounding framework for maintaining integral assignments with limited additional load. It covers edge deletions and maintaining an integral matching without explicitly storing the full slot graph.

2.1 Maintaining a Fractional Assignment

  • Long history suffixes create a 1+Θ(ϵ) job-machine flow gap, enabling expansion to bound levels by poly(log n,1/ϵ) and achieve near-linear total update time.The history graph preserves records of flow events even after edge deletions; averaging over level suffixes addresses the long historical-flow tail that can mislead single-node analysis.Source: §2.1 · pp. 6–9

2.2 Rounding the Dynamic Fractional Assignment

  • A dynamic fractional assignment with maximum load Γ and maximum job weight W rounds to an integral assignment with maximum load (1 + ϵ)Γ + W.Source: §2.2 · p. 9
  • The prior [KLS23] approach achieves small recourse but faces unstable slot-graph edges and no known fast fully dynamic matching method from expansion alone.Source: §2.2 · p. 10
  • With implicit access to the gap-guaranteed y, random augmenting paths yield ˜O(1/ϵ) update time and length O(log(n)/ϵ) with high probability.The walk samples neighboring slots proportional to y; the slot-side slack ensures that an Ω(ϵ) fraction of remaining probability reaches unmatched slots at each step.Source: §2.2 · pp. 10–11
  • A fractional assignment with a gap guarantee is stronger than graph H’s vertex expansion and enables maintaining a left-perfect matching.Source: §2.2 · p. 11
  • The algorithm maintains only the integral matching and compact interval structures, samples y-edges implicitly, and repairs unmatched jobs with short random augmenting paths.Interval data structures support finding O(1) eligible slots for a job-machine pair and sampling a neighbor according to the y-distribution; slots’ stability limits updates despite implicit changes to H.Source: §2.2 · p. 11
  • The combined algorithm handles edge deletions with near-linear total update time and integral load (1 + O(ϵ))Γ + W.It uses a fractional assignment with load 1 + O(ϵ) and bounded total change.Source: §2.2 · p. 11
  • The rounding framework is black-box and applies to decremental, incremental, or fully dynamic fractional algorithms, including the incremental algorithm of Bhattacharya, Kiss, and Saranurak [BKS23b].Source: §2.2 · p. 11

3 Preliminaries

This section fixes the weighted bipartite-graph model, defines flow and assignment quantities, and specifies the restricting updates considered in the dynamic setting.

3 Preliminaries

  • The input is a bipartite graph of jobs and machines, with each job assigned a weight in [1, W].For a job set J′, w(J′) is the sum of its job weights; N(v) denotes a node’s neighbors.Source: §3 · p. 11
  • A flow gives each edge a nonnegative assignment amount; weighted flow into a machine is its load, and the flow’s load is the maximum machine load.The total flow sent by a job and absorbed by a machine are denoted x(j) and x(i), respectively.Source: §3 · p. 12
  • An assignment sends one unit of flow from every job, an integral assignment uses only 0–1 edge values, and an ϵ-fractional assignment sends each job at least 1/(1 + ϵ).Source: §3 · p. 12
  • The load-balancing objective is to minimize assignment load; Optf and Opt denote the optimal fractional and integral loads, respectively.Source: §3 · p. 12
  • Restricting updates delete existing edges or insert jobs with their weights and incident edges; m counts edges ever present and n counts jobs and machines at the end.For convenience, the algorithm is assumed to know n in advance.Source: §3 · p. 12
  • For exposition, the parameters L and κ are assumed to be integers.Source: §3 · p. 12

4 Core Components

The algorithm combines a decremental fractional-assignment procedure with a rounding scheme for integral assignments. The fractional procedure maintains a load bound or certifies that the guessed optimum is too small, while rounding adds only a controlled load overhead.

4 Core Components

  • The rounding scheme converts an ϵ-fractional assignment into an integral assignment with only a small overhead in approximation guarantee and total update time.It supports fully dynamic vertex and edge updates to the fractional assignment.Source: §4 · pp. 12–13
  • The fractional procedure either maintains an ϵ-fractional assignment with load at most β(1 + ϵ) · Γ or certifies Optf(G, w) > Γ.The algorithm is deterministic and operates on restricting updates.Source: §4 · p. 12
  • The fractional algorithm has total update time ˜O(m/ϵ4), hiding polylogarithmic factors in m, n, W, and 1/ϵ.The rounding scheme maintains integral load at most (1 + O(ϵ))Γt + W with total update time ˜O((m + U)/ϵ3) with high probability.Source: §4 · p. 13
  • (2 + ϵ)-approximate integral load is achieved by rounding, with a stronger bound of (1 + ϵ) · Opt + W.Because W ≤ Opt, this is at most (2 + ϵ) · Opt.Source: §4 · p. 13

5 Maintaining an ϵ-Fractional Assignment: The Algorithm

The algorithm adjusts edge flows by boosting jobs or whacking machines until it restores an ϵ-fractional assignment within the target load, or certifies Optf(G, w) > Γ. Its flow changes are governed by job and machine levels, which increase monotonically.

5 Maintaining an ϵ-Fractional Assignment: The Algorithm

  • On edge deletion it removes that edge’s flow; on job insertion it initializes the new job’s level and incident-edge flows before repeating the correction process.The process stops when the assignment meets the target or a job or machine reaches the level threshold.Source: §5 · p. 15
  • When the assignment violates the target, the algorithm whacks an overfull machine or boosts a job whose total flow is too small, prioritizing whacks.Boost multiplies incident flows by (1 + ϵ), while Whack multiplies them by (1 + ϵ)^-1.Source: §5 · pp. 14–15
  • If any job or machine reaches level 10κ(7L + α), the algorithm terminates and declares Optf(G, w) > Γ; levels never exceed that threshold.The algorithm states that this termination condition occurs only if Optf(G, w) > Γ.Source: §5 · pp. 15–16
  • For each edge, flow increases by a multiplicative (1 + ϵ) factor when its job is boosted, and decreases by that factor when its machine is whacked; corresponding levels increase by one.Job and machine levels are initialized to zero; they count boosts and whacks, respectively, and increase monotonically.Source: §5 · pp. 14–15
  • For every job, total flow remains below 1, and every edge flow remains in [0, 1).The job-flow bound follows from boosting only when its total flow is below (1 + ϵ)^-1.Source: §5 · pp. 15–16

6 Maintaining an ϵ-Fractional Assignment: The Analysis

This section analyzes the algorithm’s correctness and total update time, using monotone history graphs and event-based flow accounting to bound flow and show job and machine levels remain below the termination threshold when Optf(G, w) ≤ Γ. It completes the proof of Lemma 6.11 by combining earlier claims with a bound for ϵ < 1/100.

6 Maintaining an ϵ-Fractional Assignment: The Analysis

  • The algorithm’s total update time is ˜O(m/ϵ4), with Boost and Whack calls paid for by tokens assigned to incident edges.Each edge receives at most ˜O(1/ϵ4) tokens over the algorithm’s duration.Source: §6 · p. 16

6.2 Establishing the Correctness of Our Algorithm: Proof of Lemma 6.2

  • When Optf(G, w) ≤ Γ, all job and machine levels remain below 10κ(7L + α); per-level flow bounds and geometric expansion establish this cap.The expansion argument cannot repeat for more than logarithmically many iterations.Source: §6 · p. 16, §6.2 · p. 18

6.1 The History Graph G = (J ∪M, E) and the History Flow z : E →R≥0

  • The history graph records job and machine level nodes and preserves past fractional assignments as history flows; its nodes, edges, and edge flows evolve monotonically.The algorithm itself is oblivious to these analysis-only constructs.Source: §6 · p. 16, §6.1 · p. 17

6.2 Establishing the Correctness of Our Algorithm: Proof of Lemma 6.2

  • In case (b), the proof obtains a nonempty high-level machine set and a contradiction with Equation (9) whenever mnW exceeds an absolute constant independent of ϵ.The nonempty set is established before deriving the contradiction.Source: §6.2 · p. 23

6.2.1 Bounding the Total Flow out of Job-Level Nodes: Proof of Lemma 6.9

  • At job-level nodes, flow accounting bounds the initial flow at each entered level by 1 and the cumulative loss by Fgain + 1.Flow sent when a job first enters a level is at most 1; Claim 6.17 gives Floss ≤ Fgain + 1.Source: §6.2.1 · p. 24

6.2.2 Bounding the Total Weighted Flow into Machine-Level Nodes: Proof of Lemma 6.11

  • Immediately after machine i gets whacked, its weighted flow wx(i) exceeds β · Γ, and Wgain ≥Wloss −(3 + ϵ2)Γ.Source: §6.2.2 · pp. 25, 27
  • When a machine is whacked, x(j, i) is scaled by (1 + ϵ)^−1 for every neighboring job j.The resulting increase in Wloss is considered in bounding the total weighted flow into machine-level nodes.Source: §6.2.2 · pp. 27–28
  • Each increase in Wgain is charged to a (1 + ϵ)/ϵ-unit increase in weighted gain at a machine-level node.A boost changes Wgain by ϵλ and the corresponding weighted gain by (1 + ϵ)λ.Source: §6.2.2 · p. 28
  • The proof concludes Lemma 6.11 from Claim 6.23, Corollary 6.29, and Equation (9).The preceding inequalities use ϵ < 1/100.Source: §6.2.2 · p. 28

7 Fully Dynamic Rounding for Load Balancing

The section presents a dynamic rounding framework that converts fractional load-balancing assignments into integral ones with additive maximum-job-weight overhead, using robust slot decomposition and dynamic matching maintenance. It also bounds the data structure’s update costs and shows how an augmenting random walk efficiently matches unmatched left nodes.

7 Fully Dynamic Rounding for Load Balancing

  • The randomized rounding algorithm maintains an integral assignment with maximum load at most (1 + O(ϵ))Γt + W and total update time ˜O((m + U)/ϵ3), with high probability against an adaptive adversary.Here Γt is the fractional assignment’s maximum load, W is the maximum job weight, and U counts edge updates to the fractional assignment.Source: §7 · p. 28
  • The framework extends the online slot-decomposition of Krishnaswamy et al. [KLS23] to dynamic updates, then uses a job-perfect matching to obtain load at most Γ(1 + 5ϵ) + W.A machine is represented by slots, and matching each job to a slot assigns it to that slot’s machine; the decomposition remains robust under updates to the fractional assignment.Source: §7 · p. 29

7.1 Proof of Lemma 7.4

  • The deterministic slot-decomposition maintenance takes ˜O(1/ϵ2) amortized time per fractional-edge update and ensures an ϵ-approximate decomposition with O(1) neighboring slots per job-machine pair.Its bucket-based construction localizes neighborhood changes to the updated job or slots whose weights or membership change.Source: §7 · p. 30, §7.1 · p. 34

7 Fully Dynamic Rounding for Load Balancing

  • A randomized matching algorithm maintains a job-perfect matching when job-side fractional degrees are at least 1 − ϵ and slot-side degrees at most 1 − 2ϵ, in ˜O(m/ϵ) total update time.It uses ˜O((D + n)/ϵ) oracle queries with high probability against an adaptive adversary; the rounding framework obtains the required matching through random augmenting walks.Source: §7 · pp. 29–30

7.1 Proof of Lemma 7.4

  • The rounding algorithm takes ˜O(U/ϵ^2) update time and, by Claim 7.11, at most Δ(x, l1) slots undergo updates.The claim assumes x undergoes U edge updates.Source: §7.1 · p. 34
  • A fractional edge-weight change Δ causes O(Δ/ϵ^2) amortized slot insertions or deletions, while bucket merges or splits and constraint-driven resets are bounded by O(ϵΔ) and O(Δ/ϵ), respectively.Each reset triggered by a slot violating weight constraints results in O(1/ϵ) slot updates.Source: §7.1 · pp. 34–35

7.2 Proof of Lemma 7.5

  • An augmenting random walk matches an unmatched left node in O(log n/ϵ) time and oracle queries with probability 1 − 1/poly(n), and runs at most n times for insertions and again when a left node becomes unmatched.At matched left nodes, it samples a neighbor proportionally to fractional edge weight; at matched right nodes, it follows the matching edge, terminating at an unmatched right node.Source: §7.2 · p. 35

A Dynamic Matching via Dynamic Load Balancing

A fast dynamic fractional load-balancing algorithm would yield a fully dynamic approximate matching algorithm with near the same update time. The reduction builds this result through phased matching maintenance and a sampled-graph procedure for finding large matchings in induced subgraphs.

A Dynamic Matching via Dynamic Load Balancing

  • An O~(T)-amortized-update-time dynamic fractional load-balancing algorithm implies an O~(T)-amortized-update-time (1−ϵ)-approximate matching algorithm, with high probability against an oblivious adversary.The load-balancing premise is for unweighted instances and maintains an ϵ-fractional assignment.Source: A Dynamic Matching via Dynamic Load… · pp. 39–40
  • The reduction maintains matchings in phases, recomputing near-maximum matchings at phase starts and accounting for edge deletions between recomputations.Phases have length Θ_ϵ(n); the amortized overhead per original update is O~(T).Source: A Dynamic Matching via Dynamic Load… · pp. 40, 43
  • Each induced-subgraph query uses a temporary load-balancing instance and returns a maximal matching from a sampled subgraph.The temporary instance has optimum load 1 with high probability, and the sampled matching has size poly(δ)·µ(G[U]).Source: A Dynamic Matching via Dynamic Load… · pp. 40–43
  • A sampled graph with O~(n) edges contains a matching of size Ω(δn) with high probability when the queried subgraph has matching size at least δn.The maximal matching computed in the sampled graph inherits the Ω(δn) lower bound.Source: A Dynamic Matching via Dynamic Load… · p. 42

B 2 −ϵ-Approximation Hardness for Full Dynamic Load Balancing

Assuming the OMv conjecture, fully dynamic load balancing cannot achieve a better-than-2 approximation with both sublinear amortized update time and sublinear query time. The proof encodes online Boolean matrix-vector queries as a load-balancing instance with an optimum-load gap of 1 versus 2.

B 2 −ϵ-Approximation Hardness for Full Dynamic Load Balancing

  • Under the OMv conjecture, no fully dynamic (2−ε)-approximation has polynomial preprocessing, O(N^(1−δ)) amortized update time, and O(N^(2−δ)) query time.If the maintained assignment value is explicitly available after each update, the update-time bound alone is ruled out.Source: B 2 −ϵ-Approximation Hardness for Full… · p. 43
  • The reduction encodes each online vector pair so that u⊤Av=1 gives optimum load 1, while u⊤Av=0 gives optimum load 2.The construction updates at most 2n edges for each new pair.Source: B 2 −ϵ-Approximation Hardness for Full… · p. 44
  • O(n^(3−δ)) total online time after polynomial preprocessing would solve OuMv in truly subcubic time, contradicting the OMv conjecture.The constructed graph has N=Θ(n) vertices.Source: B 2 −ϵ-Approximation Hardness for Full… · pp. 43–44
Loading 2610.23768v1…