Dynamic k-center clustering with lifetimes
This work addresses the problem of efficiently clustering evolving datasets for applications in learning systems and data summarization, representing an incremental advance by bridging existing dynamic settings.
The paper tackles the dynamic k-center clustering problem by introducing a setting with lifetimes, where deletion times are known upon point arrival, bridging sliding window and fully dynamic settings. It presents deterministic algorithms achieving (2+ε)-approximation with amortized update time and (6+ε)-approximation with worst-case update time under certain conditions.
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.