Dynamic k-Median with Worst-Case Update Time and Recourse

arXiv:2611.17296 · cs.DS · Submitted 2026-11-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Dynamic k-Median with Worst-Case Update Time and Recourse".

Jane: Here's the gist of the paper. The paper presents a fully dynamic metric k-median algorithm designed to handle unit-weight client insertions and deletions while maintaining at most k centers chosen from current client locations.

Tom: The core result, Theorem 1.1 (and subsequently Theorem 9.10), establishes the existence of a randomized algorithm that achieves a constant-factor approximation guarantee over any prescribed finite adaptive update sequence with high probability (1-delta).

Jane: The complexity guarantees are highly favorable: the worst-case update time is O(k) or O(n+k) depending on the specific formulation, and the worst-case center recourse is O((1 + delta) 3), where delta is the aspect ratio of the underlying metric space.

Tom: Crucially, these resource bounds hold deterministically for every execution, while the approximation guarantee holds simultaneously over any finite adaptive sequence with high probability.

Paper summary: Tom: So, the core thesis of this paper is that they want a randomized algorithm for this fully dynamic metric k-median problem.

Jane: It says that after every update—whether someone joins or leaves—the algorithm must keep at most k centers chosen from where the clients currently are.

Tom: They provide two main guarantees: one for the update time and one for how many centers you have to move after an update.

Jane: The key results, Theorem one point one and later Theorem nine point one zero, show they get a constant-factor approximation guarantee over any sequence of updates with high probability, which is good because it holds even when things change adaptively over time.

Lu: What's interesting about the structure is that they break it down into six steps: lazy updates, protected cores, robust rebuilding, gradual migration, background work and weighted summaries.

Meng: That sounds like a lot of moving parts to manage in a real system.

Lalam: But the crucial part for us is the resource bounds they settle on: worst-case update time is O(k) or O(n+k) depending on how you look at it, and center recourse is O((one + Delta) three), where Delta is that aspect ratio of the metric space <ref:2611.17296#pg1>.

Tom: So, the paper claims they get this constant-factor approximation with those specific worst-case bounds deterministically for every execution.

Jane: It's a strong claim because it means you don't have to worry about things taking forever or blowing up on any given run.

Conclusion: Tom: Looking at the paper "Dynamic k-Median with Worst-Case Update Time and Recourse" and the authors, Chenglin Fan is the lead researcher here.

Jane: What this paper really means for us is it shows how you can design a system that handles continuous changes in data, like sensor readings or network traffic, without needing to completely recompute everything every single time.

Lu: It confirms that you can have these strong worst-case bounds on update time and center recourse even when the underlying space has weird geometry represented by Delta.

Meng: For production, having an update time that is O(k) would be fantastic because it means the system stays responsive even if we have a lot of clients.

Lalam: The paper proves this dynamic metric k-means result with update time O(k), recourse O((one + Delta) three), and initialization cost of O(k(n0 + k)) <ref:2611.17296#pg1>.

Tom: It gives us a solid foundation for building these kinds of robust, adaptive clustering or facility location systems that are meant to run in real time.

Chenglin Fan

cs.DS

Submitted: 2026-11-12

Updated: 2026-11-12

Comments: 81 pages

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 93/100

The gist: The paper presents a fully dynamic metric k-median algorithm designed to handle unit-weight client insertions and deletions while maintaining at most k centers chosen from current client locations.

Key concepts

Fully Dynamic Metric k-Median
This is an algorithm designed to maintain a set of k facility locations (centers) in a metric space as client data (points) is constantly added or removed. The goal is to ensure the chosen centers provide a good approximation of the optimal solution despite these continuous changes.
Weighted Summary
A key component that keeps track of important client data efficiently. This summary is designed to be small and easy to maintain, allowing the algorithm to quickly process updates without needing large batch record changes, which keeps the maintenance work low.
Recourse
In this context, recourse refers to the computational cost or effort required by the algorithm when a change (like an update) occurs. The paper proves that this cost is bounded by $O((1 + ext{log } ext{Delta})^3)$, meaning the algorithm remains fast even under complex updates.
Squared-Cost Formulation
This involves using a specific mathematical way to measure the error of the k-median solution, focusing on squared distances. Analyzing this formulation allows researchers to establish strong bounds on how close the found solution is to the true optimal solution.

Terminology

Summary

The paper presents a fully dynamic metric k-median algorithm designed to handle unit-weight client insertions and deletions while maintaining at most k centers chosen from current client locations. p. 0

Where the paper says it

Dynamic k-Median with Worst-Case Update Time and Recourse Chenglin Fan November 13, 2026 Abstract We study fully dynamic metric k-median under unit-weight client insertions and deletions. After each update, the algorithm must maintain at most k centers chosen from the current client locations.

The core result, Theorem 1. p. 3
Where the paper says it

The hidden constant is absolute. The worst-case update time, recourse, and initialization bounds are those of Theorem 1.

1 (and subsequently Theorem 9. p. 3
Where the paper says it

The hidden constant is absolute. The worst-case update time, recourse, and initialization bounds are those of Theorem 1.

10), establishes the existence of a randomized algorithm that achieves a constant-factor approximation guarantee over any prescribed finite adaptive update sequence with high probability (1-delta). p. 0
Where the paper says it

We give a randomized constant-factor approximation algorithm with Oe(k) worst-case update time and O((1 + log ∆) 3 ) worst-case center recourse, where ∆ is the aspect ratio of the underlying metric space. The approximation guarantee holds simultaneously over any prescribed finite adaptive update sequence with high probability, while the update time and recourse bounds hold on every execution.

The complexity guarantees are highly favorable: the worst-case update time is O(k) or O(n+k) depending on the specific formulation, and the worst-case center recourse is O((1 + delta) 3), where delta is the aspect ratio of the underlying metric space. p. 0

Where the paper says it

After each update, the algorithm must maintain at most k centers chosen from the current client locations. We give a randomized constant-factor approximation algorithm with Oe(k) worst-case update time and O((1 + log ∆) 3 ) worst-case center recourse, where ∆ is the aspect ratio of the underlying metric space.

Crucially, these resource bounds hold deterministically for every execution, while the approximation guarantee holds simultaneously over any finite adaptive sequence with high probability. p. 0
Where the paper says it

We give a randomized constant-factor approximation algorithm with Oe(k) worst-case update time and O((1 + log ∆) 3 ) worst-case center recourse, where ∆ is the aspect ratio of the underlying metric space. The approximation guarantee holds simultaneously over any prescribed finite adaptive update sequence with high probability, while the update time and recourse bounds hold on every execution.

Initialization takes O(k(n 0 + k)) time. p. 2
Where the paper says it

The hidden constant is absolute. Initialization on n0 clients takes Oe(k(n0 + k)) time.

The algorithm is structured in six steps: lazy updates, protected cores, robust rebuilding, gradual migration, background work, and weighted summaries. p. 5

Where the paper says it

Step 1 lazy updates 2k facilities Step 2 protected cores k-facility budget Step 3 robust rebuilding amortized bounds Step 4 gradual migration worst-case recourse Step 5 background work worst-case time Step 6 weighted summaries Oe(k) time Figure 1: The six-step construction. Steps 1–5 operate on an explicit weighted instance.

The final result combines the guarantees derived from these steps to yield a fully dynamic constant-factor approximation with O(k) worst-case update time and O((1 + delta) 3) worst-case center recourse. p. 2
Where the paper says it

Reference Approximation Update time Recourse Resource bounds [BCG+24] O(1/ε) Oe(k 1+ε ) Oe(k ε ) Amortized [BCF25] O(1) Oe(k) O(log2 ∆) Amortized This paper O(1) Oe(k) O((1 + log ∆) 3 ) Worst case Table 1: Selected simultaneous guarantees for fully dynamic metric k-median. The final column applies to both update time and recourse.

A significant component involves a weighted summary (Step 6) which is key to achieving the final bound. This summary is designed to keep the input to a solver small without incurring large batch record changes, leading to bounded maintenance work per update (O(k)). p. 3

Where the paper says it

A packing argument shows that one record edit can directly affect only O(1 + log ∆) existing certificates. Consequently, the work and center changes of each repair batch can be bounded in terms of that batch’s own edits and proposed center changes (Theorem 5.

The composition of this summary guarantee with the guarantees from Step 5 results in the stated resource bounds and approximation quality. p. 2
Where the paper says it

Reference Approximation Update time Recourse Resource bounds [BCG+24] O(1/ε) Oe(k 1+ε ) Oe(k ε ) Amortized [BCF25] O(1) Oe(k) O(log2 ∆) Amortized This paper O(1) Oe(k) O((1 + log ∆) 3 ) Worst case Table 1: Selected simultaneous guarantees for fully dynamic metric k-median. The final column applies to both update time and recourse.

The analysis also explores related concepts, including dynamic weighted summaries (Theorem 8. p. 9

Where the paper says it

Step 6 removes it using a small weighted summary; see Section 7 for the formal schedule. 6 Step 6: Dynamic Weighted Summaries Step 5 achieves worst-case update time Oe(n + k) for a weighted instance, where n is the number of occupied locations.

12), which show that a weighted summary Q can be maintained such that its support is bounded by O(k), its total weight is bounded by 2P, maintenance work is O(k), and weighted record edits are O(1) per update. p. 4
Where the paper says it

We therefore prove a separate packing bound on the cost of representing the original clients by the current weighted summary. This allows us to preserve the clustering approximation while maintaining both small support and a constant number of record edits per update (Lemmas 8.

Furthermore, the composition of such a solver with an algorithm supporting arbitrary positive integer record weights leads to bounds on update time and recourse.

The analysis further delves into squared-cost formulations (Theorem 9. p. 4

Where the paper says it

In particular, the robustification analysis in [BCF25, Section 14. 3] bounds the total cost over an update sequence.

8), showing that arbitrary weighted-record edits admit O(n+k) worst-case time and O(L cubed delta) recourse, with a proper output of at most k facilities. p. 8
Where the paper says it

Executing O((1 + log ∆) 3 ) transitions per update over Θ(B) edits therefore gives the same worst-case center recourse bound; proper projection preserves it for published client centers. However, computing the target and preparing the path may still take excessive time at one update.

Lemma 9.9 provides bounds on the squared transportation error (E 2) relative to the optimal solution cost (OPT k,2(P)), showing that E 2 at most a 2 OPT k,2(P), where a 2 is an absolute constant. p. 5
Where the paper says it

Indeed, edited locations incur zero connection cost, while the cost at all other locations cannot increase. Applying this observation to an optimal solution for Q also gives Fj+h(P) ≤ Fj(Q).

This leads to Theorem 9. p. 3
Where the paper says it

The hidden constant is absolute. The worst-case update time, recourse, and initialization bounds are those of Theorem 1.

10, confirming the fully dynamic metric k-means result with update time O(k), recourse O((1 + delta) 3), and initialization cost O(k(n 0 + k)). p. 0
Where the paper says it

Dynamic k-Median with Worst-Case Update Time and Recourse Chenglin Fan November 13, 2026 Abstract We study fully dynamic metric k-median under unit-weight client insertions and deletions. After each update, the algorithm must maintain at most k centers chosen from the current client locations.

The paper also compares the results to Euclidean centroids (Corollary 9. p. 3

Where the paper says it

In this case, the proper squared optimum is at most twice the optimum obtained by allowing arbitrary Euclidean centroids. Thus the corollary also gives a constant approximation against the unrestricted centroid benchmark (Corollary 9.

11), showing that under fixed-universe Euclidean assumptions, the output cost is at most 2A 2 OPT Euc, k(P). p. 2
Where the paper says it

The known distance bound applies to the fixed metric space, including locations occupied in the past, rather than only to the current client support. These assumptions are used in the snapshot and projection arguments.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Worst-case update time is bounded by Oe(k) for fully dynamic metric k-median, meaning that after every client insertion or deletion, the algorithm maintains a proper set of at most k centers in constant time relative to the number of clients and updates.

  2. Center recourse is bounded by O((1 + log Delta) 3), which means that replacing one center by another costs at most this amount, ensuring the solution remains stable under adversarial changes in the metric space aspect ratio Delta.

  3. The system can maintain a constant-factor approximation guarantee over any prescribed finite adaptive update sequence with high probability, meaning the approximation quality is guaranteed regardless of how updates are chosen adaptively.

  4. The algorithm maintains at most k centers chosen from current client locations, and it does so while serving the current input, fulfilling the worst-case requirement that The old solution must remain a good approximation until the replacement is ready.

  5. For Euclidean clustering (k-means), the system can maintain a constant factor approximation with Oe(1) amortized recourse and O((1 + log Delta) 3) worst-case update time, offering specific performance guarantees for squared distances.

  6. The system utilizes a six-step construction that combines lazy updates, protected cores, robust rebuilding, gradual migration, background work scheduling, and weighted summaries to achieve the final Oe(k) bound on update time by reducing the problem to a smaller instance with only O(1) weighted-record edits per original client update.

  7. The system employs geometric annotations (anchors and proxies) with strong reset times and offset conditions to control anchor relocations, preventing long cascades of moves that could otherwise trigger excessive center changes.

  8. The system uses a budget-preserving migration order that guarantees intermediate sets obey the distance bound d(x, S) <= 2d(x, A) + d(x, B), allowing for controlled transitions between core solutions while respecting the k-center budget.

  9. The system schedules reconstruction and migration across available updates in a four-stage process to meet deadlines; for large windows, this involves refreshing the old solution on the frozen input before choosing a new protected core and preparing the migration path in stages.

  10. A dynamic weighted summary is maintained using multiple sampling layers, represented by Oe(k) occupied locations, which preserves the clustering approximation by bounding transportation costs using a geometric tail-packing argument to E = O(OPTk(P)).

  11. The system can handle client updates where a single change affects only O(1) weighted records by temporarily allowing clients to be represented in one or two active tokens, ensuring that each original client update produces only O(1) weighted-record edits.

Abstract

We study fully dynamic metric k-median under unit-weight client insertions and deletions. After each update, the algorithm must maintain at most k centers chosen from the current client locations. We give a randomized constant-factor approximation algorithm with O(k) worst-case update time and O((1+ Δ) 3) worst-case center recourse, where Δ is the aspect ratio of the underlying metric space. The approximation guarantee holds simultaneously over any prescribed finite adaptive update sequence with high probability, while the update time and recourse bounds hold on every execution. We also obtain the same asymptotic guarantees for metric k-means.

Sources

Related papers