CS Paper Radar

Dynamic Load Balancing under Restricting Updates

Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak

cs.DS ·submitted 2026-10-16 17:07 UTC · v1

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].

Closest papers

Nearest neighbours by meaning across the whole index.

Online and Incremental Fractional Vertex Cover on Trees

cs.DS ·2026-08-25 ·Júlia Baligács, Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Grzegorz Gutowski +3 more
publishedtheory similarity 0.66
Abstract

In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0,1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model. In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.

0.46

Matching in Random-Order Streams via Historical Deletion Bounds

cs.DS ·2026-11-12 ·Alireza Farhadi, Mohammadtaghi Hajiaghayi, Mohammad Mahdavi
theory similarity 0.63
Abstract · 38 pages, including appendices

We study maximum matching when the edges of a fixed graph arrive in a uniformly random order. For any fixed $\varepsilon>0$, we give a one-pass algorithm that achieves, with high probability over the arrival order, approximation ratios of $0.71295$ for unweighted graphs and $0.71295-\varepsilon$ for weighted graphs, using near-linear space with an explicit charge for weight precision. Both approximation ratios hold for bipartite and general graphs. The algorithm does not require the stream length or the weight range in advance. The main structural ingredient is a historical deletion inequality for weighted matchings. The deletion price of a vertex set is the decrease in maximum matching weight when that set is removed. We bound the sum of these prices for pairwise disjoint vertex sets, even when each price is evaluated at a different stage as edges are added to the graph. Applied to the usual unfolding of integer weights, it transfers a bipartite cardinality certificate to an original weighted matching, even when the original graph is not bipartite. This transfer preserves the approximation coefficient. We combine this transfer with a refined analysis of fractional matchings in the two auxiliary graphs arising in the transfer theorem. An exact rational linear-programming certificate proves the stated constant for every feasible graph profile. The approximation guarantees and the new structural results are formally verified in Lean.

0.40

The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing

cs.DS math.OC ·2026-09-03 ·Adam Y. Shavit
code/data similarity 0.63
Abstract · 43 pages, 9 figures. v3: the beta < 1/2 seven-machine witness is certified in exact rational arithmetic; the strict-rule endpoint at beta = …

Wang and Sitters' 11/6-approximation for graph balancing (each job allowed on at most two machines) is not one algorithm but a set of permitted executions. Step 1 may return any feasible solution of the fractional relaxation. Step 3 may match remaining jobs to the rounding's slots in many ways. We determine exactly what that latitude permits: ratios arbitrarily close to 11/6, none reaching it, so 11/6 is the least constant bounding every permitted run. We then determine the worst-case guarantee, against the optimum itself, as a function of the big-job threshold beta, the fractional share at or above which Step 2 assigns a job. On Wang and Sitters' own range 1/2 < beta < 1 the guarantee is exactly max{3/2 + beta/2, 5/2 - beta}. We extend the same eligibility rule to 0 < beta <= 1/2, outside the range they state. There a big job's two shares can both reach the threshold, so Step 2 acquires a third choice. We determine it too: exactly 3/2 + (1-beta)floor(1/beta), hence unbounded as beta falls. The worst-case ratio is therefore known at every threshold in (0,1), and attained at none. Consequently 2/3 is the unique optimal threshold, and the guarantee jumps at one half and again at every threshold 1/k below it, rather than degrading smoothly. A companion note examines changes that leave the constant unchanged.

0.45

Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6

cs.DS math.OC ·2026-09-09 ·Adam Y. Shavit
code/data similarity 0.62
Abstract · 52 pages, 11 figures. v2: new results: where the cut-term bound 3/2+1/(r+1) is attained on the three-path family (correcting v1), and strong…

Wang and Sitters' rounding scheme for graph balancing (each job allowed on at most two machines) keeps the makespan, the busiest machine's load, within 11/6 of the optimum, and a companion note shows that no smaller constant holds. One suspected cause is Step 3's freedom to match leftover jobs to slots in any valid way. We show that removing that freedom does not improve the constant. An idealized oracle that always picks the valid matching with the smallest makespan still has worst-case constant exactly 11/6 against the optimum. Both natural 7/4 bounds for it, against the relaxation's target and against the optimum, are false. Requiring Step 1 to return a vertex (corner) of the relaxation does not help when that vertex is chosen adversarially. The loss therefore does not come from Step 3's freedom alone. We also prove a reduction confining every overload above 7/4 to two shapes, give a seven-machine instance on which the natural two-phase repair fails, and prove a strict 7/4 bound on the generalized three-path family.

0.39

A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size

cs.DS math.OC ·2026-08-13 ·Adam Y. Shavit
theorycode/data similarity 0.62
Abstract · 37 pages, 12 figures, 1 table. v3: corrects the infeasibility-verdict count behind the six-machine sweep (4,228,054, not 4,231,347), a false…

Restricted assignment minimizes makespan, the busiest machine's load, when each job has one size and a set of allowed machines. Its tightest studied relaxation is the configuration linear program, which fractionally gives each machine whole job sets that fit. Its integrality gap, the worst-case ratio of integral optimum to relaxation value, is open in general. On two-weight graph balancing (sizes 1 and 2, each job allowed on at most two machines) the gap is known: Jansen, Land, and Maack (2016) give both bounds. Their Table 1 instance attains 3/2, and their Corollary 11 bound of 2-s/b for sizes s < b matches it at {1,2}. We ask how small such an instance, a witness, can be. We give a six-job witness I* on the complete graph on four machines: unit jobs form a cycle through all four, and two weight-2 jobs take the remaining edges. I* has integral optimum 3 against relaxation value 2, one job fewer than the smallest earlier witness of this class. We prove I* minimum and unique at its size, on any number of machines: no instance with at most five jobs reaches gap 3/2, and at six jobs I* is the only witness, up to relabeling machines and adding unusable machines. At seven jobs uniqueness fails: we classify all thirteen witnesses, including the Jansen-Land-Maack instance. Eight jobs give 154, nine 1,662. At least four machines are necessary. Kartak et al. (2015) classified the extremal non-round-up instances of the same relaxation in one-dimensional cutting stock for small demand; the Discussion relates them. Recognizing witnesses at relaxation value 2, shared by all ours, is coNP-complete, so no min-max characterization with polynomially checkable conditions exists unless NP = coNP. Every feasibility decision behind the exhaustive claims was made twice, in floating-point and exact rational arithmetic, with identical results. We accept the pipeline's negatives only after it rediscovers I*.

0.64

Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified Framework

cs.DS ·2026-11-01 ·Jiale Chen
similarity 0.61
Abstract · Abstract shortened due to arXiv requirements

We study the $(1-\varepsilon)$-approximate maximum weight matching problem in general graphs with $n$ vertices and integer edge weights in $[1,W]$. For $W=n^{O(1)}$, we obtain faster algorithms in the semi-streaming and dynamic settings: (1) Semi-streaming: Deterministic $O(\varepsilon^{-2})$-pass and $O(\varepsilon^{-2}\log(1/\varepsilon))$-pass algorithms for unweighted and weighted matching. (2) Incremental: A deterministic algorithm for weighted matching processing $m$ edge insertions in total time $O((m\varepsilon^{-3}+n\varepsilon^{-6})\log^3 n)$. (3) Decremental: A randomized algorithm for weighted matching processing all edge deletions from an $m$-edge graph in total time $O((m\varepsilon^{-8}+n\varepsilon^{-47})\log^{O(1)}n)$ with high probability. (4) Fully dynamic: A deterministic reduction from weighted matching in general graphs to unweighted matching in bipartite graphs incurring $O(\varepsilon^{-4}\log^{O(1)}(1/\varepsilon))$ multiplicative update-time overhead, independent of $n$. Underlying these results is a unified framework that reduces the problem to repeatedly solving two simpler matching subproblems: a $(1-\varepsilon)$-approximate maximum weight matching on a sparse subgraph with $O(n/\varepsilon)$ edges, and a constant approximation on the remaining edges. The framework builds on dual entropy regularization, a smoothing technique underlying efficient solvers for packing linear programs. To handle the exponentially many odd-set constraints, we adapt the smoothing technique to regularize only the vertex duals and develop a new cut partition that preserves odd-set feasibility during optimization.

0.16

Consistency-Robustness Tradeoffs for Online Bipartite Allocation with Multiple Stages

cs.DS ·2026-09-14 ·Alexander Lindermayr, Nicole Megow, Lauren Paul
similarity 0.61
Abstract

We study learning-augmented online bipartite allocation with multiple stages. In the $k$-stage vertex-weighted fractional bipartite matching problem, demand vertices arrive in $k$ stages, and the algorithm receives possibly inaccurate predictions of the allocation in each stage. While tight consistency-robustness tradeoffs were known for the two-stage case, no nontrivial tradeoff was known for an arbitrary number of stages. Our main result is the first consistency-robustness tradeoff for $k$-stage vertex-weighted fractional bipartite matching with predictions, for every $k\ge2$. Let $R_k=1-(1-1/k)^k$. For every $R\in[0,R_k]$, our algorithm is $R$-robust and $C_k(R)$-consistent, where $C_k(R)=k(1-R)^{1/k}+R-(k-1)$. This simultaneously recovers the known tight two-stage tradeoff and the optimal prediction-free $k$-stage competitive guarantee $R_k = C_k(R_k)$, while strictly dominating the natural randomized coin-flip baseline between these endpoints. We also present an algorithm for the classical online setting, where demands arrive one by one and the number of demands is unknown in advance. It has a consistency ratio of at least $C_\infty(R)=1+R+\ln(1-R)$ for a given robustness $R\in[0,1-1/e]$, improving the best previously known tradeoff for this problem. Finally, we extend the framework to fractional AdWords and fractional predictions. Our algorithms are based on stage-wise convex programs with carefully calibrated vertex-dependent penalties. The penalties maintain a dynamic safety reserve for each supply vertex, balancing protection against adversarial future arrivals with the ability to exploit the predicted allocation.

0.21

Scheduling to Maximize Weighted Throughput with an Active-Time Budget

cs.DS ·2026-08-29 ·Susanne Albers, G. Wessel van der Heijden
publishedtheory similarity 0.61
Abstract · 16 pages, 5 figures, To appear at WAOA 2026

We study the active-time scheduling problem with weighted throughput maximization. In this setting, a set of $n$ jobs $J$ arrive at integer release times, each with an integer processing time and integer deadline. Jobs may be preempted at integer time slot boundaries. A schedule assigns jobs to time slots, with at most $m$ jobs assigned to the same time slot. A slot is called \emph{active} if at least one job is scheduled in it. Instead of scheduling all jobs to minimize the number of active time slots, we consider the more general variant of \emph{weighted throughput} with an active-time budget $K$, where each job $j\in J$ has a weight $w_j$. The objective is to maximize the total weight of \emph{completed} jobs using at most $K$ active time slots. This means that partially scheduled jobs do not count towards the objective. The classical active-time minimization problem is recovered by asking whether all jobs can be completed within a given active-time budget. We give hardness, approximation, and exact algorithmic results. For general intervals with unbounded parallelism, we prove NP-hardness, rule out an FPTAS unless $\mathrm{P}=\mathrm{NP}$, and give a pseudo-polynomial time $Ω(1/\log K)$-approximation. For proper intervals, we prove a canonical structural lemma and obtain an exact $(nK)^{O(m)}$-time algorithm. For laminar intervals, we give an exact $f(K,m)\cdot n^{O(1)}$-time algorithm.

0.25