Dynamic k-Median with Worst-Case Update Time and Recourse
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 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 hidden constant is absolute. The worst-case update time, recourse, and initialization bounds are those of
Theorem 1. The hidden constant is absolute. The worst-case update time, recourse, and initialization bounds are those of
Theorem 1. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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 hidden constant is absolute. Initialization on n0 clients takes Oe(k(n0 + k)) time.Where the paper says it
Where the paper says it
Where the paper says it
The algorithm is structured in six steps: lazy updates, protected cores, robust rebuilding, gradual migration, background work, and weighted summaries. p. 5 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. 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.Where the paper says it
Where the paper says it
A significant component involves a 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. 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.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. 3Where the paper says it
Where the paper says it
The analysis also explores related concepts, including dynamic weighted summaries (Theorem 8. p. 9 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. 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.Where the paper says it
Where the paper says it
The analysis further delves into squared-cost formulations (Theorem 9. p. 4 In particular,
the robustification analysis in [BCF25, Section 14. 3] bounds the total cost over an update sequence. 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. 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). The hidden constant is absolute. The worst-case update time, recourse, and initialization bounds are those of
Theorem 1. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The paper also compares the results to Euclidean centroids (Corollary 9. p. 3 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. 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.Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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)).
-
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
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time