2026-07-21T14:19:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13249 2024-03-06T10:51:56Z ddc:004 open_access

Clustering Under Perturbation Stability in Near-Linear Time Agarwal, Pankaj K. Chang, Hsien-Chih Munagala, Kamesh Taylor, Erin Welzl, Emo clustering stability local search dynamic programming coreset polyhedral metric trapezoid decomposition range query 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Hsien-Chih Chang and Kamesh Munagala and Erin Taylor and Emo Welzl 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.8 urn:nbn:de:0030-drops-132492 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.8 eng https://creativecommons.org/licenses/by/3.0/legalcode