Research map / Learning theory and algorithms / Clustering

Dynamic k-center clustering with lifetimes

NeurIPS 2026 · Learning theory and algorithms › Clustering · approach: Coresets and dynamic clustering · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces the dynamic setting with lifetimes (deletion times known at arrival) for k-center and gives a deterministic (2+ε)-approximation with amortized update time and a deterministic (6+ε)-approximation with worst-case update time and sublinear memory under H-ordered ("tame") sequences.

Problem

Maintaining a k-center clustering over a dynamic point set where points arrive and expire, with each point's deletion time known upon arrival; existing work covers only sliding windows or fully dynamic (unknown deletions) settings.

Approach

Exploit known deletion times: the clustering keeps centers with latest deletion times so expensive reclustering happens rarely (amortized O(k) per guess), giving a (2+ε) algorithm; a second algorithm keeps only attractors and representatives per guess, with memory bounded by k+H under H-ordered sequences.

Key results

• Deterministic (2+ε)-approximation for dynamic k-center with lifetimes with O((log Δ/ε)·k + max_t log|X_t|) amortized update time and memory linear in active points, improving the prior O((log Δ/ε)k^2) amortized update time of the mimicked algorithm.
• Deterministic (6+ε)-approximation with worst-case O((log Δ/ε) min{k+H, |X_t|}) update time and memory O((log Δ/ε) min{k+H, max_t|X_t|}) for H-ordered sequences; O((log Δ/ε)k) when H=O(k).
• Remark shows that without reclustering the naive approach can require Θ(n^2) operations over n updates.

Surprising findings

• The paper claims its (2+ε) algorithm circumvents a metric-adaptive lower bound that rules out o(|X_t|) update time for O(1) approximation in the fully dynamic setting.

Limitations

• Trade-off lower bounds for the lifetime setting are left open.
• Recourse is O(k) for both algorithms; o(k) recourse is open.
• The (6+ε) algorithm's efficiency depends on the H-orderedness of the update sequence, i.e., only under tame sequences.

Experimental setup

Baselines: fully dynamic k-center (2+ε) algorithm with amortized O(k^2) update time general expiration streaming (6k+2+ε) algorithm sliding window k-center algorithms

Builds on: sliding window k-center algorithms fully dynamic k-center algorithms general expiration streaming model

Closest papers by meaning

• Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse (ICML 2025 · similarity 0.91)
• Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.90)
• Competitively Consistent Clustering (ICML 2025 · similarity 0.89)
• Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.88)
• Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.87)
• Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond (NeurIPS 2025 · similarity 0.86)