Fully dynamic clustering and diversity maximization in doubling metrics
Algorithms and Data Structures Symposium, 2023•Springer
We present deterministic approximation algorithms for some variants of center-based
clustering and related problems in the fully dynamic setting, where the pointset evolves
through an arbitrary sequence of insertions and deletions. Specifically, we target the
following problems: k-center (with and without outliers), matroid-center, and diversity
maximization. All algorithms employ a coreset-based strategy and rely on the same data
structure, a suitably augmented cover tree, which can thus serve queries for different …
clustering and related problems in the fully dynamic setting, where the pointset evolves
through an arbitrary sequence of insertions and deletions. Specifically, we target the
following problems: k-center (with and without outliers), matroid-center, and diversity
maximization. All algorithms employ a coreset-based strategy and rely on the same data
structure, a suitably augmented cover tree, which can thus serve queries for different …
Abstract
We present deterministic approximation algorithms for some variants of center-based clustering and related problems in the fully dynamic setting, where the pointset evolves through an arbitrary sequence of insertions and deletions. Specifically, we target the following problems: k-center (with and without outliers), matroid-center, and diversity maximization. All algorithms employ a coreset-based strategy and rely on the same data structure, a suitably augmented cover tree, which can thus serve queries for different problems at the same time. For all of the aforementioned problems, our algorithms yield approximations comparable to those achievable in the off-line setting. For spaces of bounded doubling dimension, the running times are dramatically smaller than those that would be required to compute solutions on the entire pointset from scratch after each update. To the best of our knowledge, ours are the first solutions for the matroid-center and diversity maximization problems in the fully dynamic setting.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果