# Fully-Dynamic Coresets

arXiv: https://arxiv.org/abs/2004.14891 · HTML: https://mlsanity.com/paper/2004.14891/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2020.

## Built on by (most cited first, 9 of 9)

- [Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems](https://mlsanity.com/paper/2107.00068/) (2021)
- [Near-Optimal Quantum Coreset Construction Algorithms for Clustering](https://mlsanity.com/paper/2306.02826/) (2023)
- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Fully-Dynamic Decision Trees](https://mlsanity.com/paper/2212.00778/) (2022)
- [Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees](https://mlsanity.com/paper/2302.03994/) (2023)
- [Dynamic algorithms for k-center on graphs](https://mlsanity.com/paper/2307.15557/) (2023)
- [Coresets for Clustering Under Stochastic Noise](https://mlsanity.com/paper/2510.23438/) (2025)
- [Clustering with Label Consistency](https://mlsanity.com/paper/2512.19654/) (2025)
- [Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling](https://mlsanity.com/paper/2609.06394/) (2026)

## Abstract (arXiv)

With input sizes becoming massive, coresets -- small yet representative summary of the input -- are relevant more than ever. A weighted set Cw that is a subset of the input is an varepsilon-coreset if the cost of any feasible solution S with respect to Cw is within [1 ± varepsilon] of the cost of S with respect to the original input. We give a very general technique to compute coresets in the fully-dynamic setting where input points can be added or deleted. Given a static varepsilon-coreset algorithm that runs in time t(n, varepsilon, λ) and computes a coreset of size s(n, varepsilon, λ), where n is the number of input points and 1 -λ is the success probability, we give a fully-dynamic algorithm that computes an varepsilon-coreset with worst-case update time O((log n) · t(s(n, varepsilon/log n, λ/n), varepsilon/log n, λ/n) ) (this bound is stated informally), where the success probability is 1-λ. Our technique is a fully-dynamic analog of the merge-and-reduce technique that applies to insertion-only setting. Although our space usage is O(n), we work in the presence of an adaptive adversary, and we show that Omega(n) space is required when adversary is adaptive. As a consequence, we get fully-dynamic varepsilon-coreset algorithms for k-median and k-means with worst-case update time O(varepsilon-2k2log5 n log3 k) and coreset size O(varepsilon-2klog n log2 k) ignoring log log n and log(1/varepsilon) factors and assuming that varepsilon, λ = Omega(1/poly(n)). These are the first fully-dynamic algorithms for k-median and k-means with worst-case update times O(poly(k, log n, varepsilon-1)). We also give conditional lower bound on update/query time for any fully-dynamic (4 - δ)-approximation algorithm for k-means.