Dynamic k-center clustering with lifetimes

Read full text Summarise with VIRAT
Authors: Simone Moretti, Paolo Pellizzoni, Andrea Pietracaprina, Geppino Pucci
Cited by: 0
References: 27

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

The $k$-center problem is a fundamental clustering variant with applications in learning systems and data summarization. In several real-world scenarios, the dataset to be clustered is not static, but evolves over time, as new data points arrive and old ones become stale. To account for dynamicity, the $k$-center problem has been mainly studied under the sliding window setting, where only the $N$ most recent points are considered non-stale, or the fully dynamic setting, where arbitrary sequences of point arrivals and deletions without prior notice may occur. In this paper, we introduce the dynamic setting with lifetimes, which bridges the two aforementioned classical settings by still allowing arbitrary arrivals and deletions, but making the deletion time of each point known upon its arrival. Under this new setting, we devise a deterministic $(2+\varepsilon)$-approximation algorithm with $\tilde{O}(k/\varepsilon)$ amortized update time and memory usage linear in the number of currently active points. Moreover, we develop a deterministic $(6+\varepsilon)$-approximation algorithm that, under tame update sequences, has $\tilde{O}(k/\varepsilon)$ worst-case update time and heavily sublinear working memory.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Clustering Algorithms Research Computational Geometry and Mesh Generation

Publication details

Journal / source
arXiv (Cornell University)
Publication date
24 March 2026
Language
EN
Document type
Preprint