Abstract
We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is α-stable if the underlying optimal clustering continues to remain optimal even when all pairwise distances are arbitrarily perturbed by a factor of at most α. Our main contribution is in presenting efficient exact algorithms for α-stable clustering instances whose running times depend near-linearly on the size of the data set when α ≥ 2 + √3. For k-center and k-means problems, our algorithms also achieve polynomial dependence on the number of clusters, k, when α ≥ 2 + √3 + ε for any constant ε > 0 in any fixed dimension. For k-median, our algorithms have polynomial dependence on k for α > 5 in any fixed dimension; and for α ≥ 2 + √3 in two dimensions. Our algorithms are simple, and only require applying techniques such as local search or dynamic programming to a suitably modified metric space, combined with careful choice of data structures. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000465026Publikationsstatus
publishedExterne Links
Buchtitel
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)Zeitschrift / Serie
Leibniz International Proceedings in Informatics (LIPIcs)Band
Seiten / Artikelnummer
Verlag
Schloss Dagstuhl - Leibniz-Zentrum für InformatikKonferenz
Thema
clustering; stability; local search; dynamic programming; coreset; polyhedral metric; trapezoid decomposition; range query; Theory of computation → Design and analysis of algorithmsOrganisationseinheit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Anmerkungen
Due to the Coronavirus (COVID-19) the conference was conducted virtually.