文章基本信息

标题：Clustering Under Perturbation Stability in Near-Linear Time
本地全文：下载
作者：Pankaj K. Agarwal ; Hsien-Chih Chang ; Kamesh Munagala 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：182
页码：1-16
DOI：10.4230/LIPIcs.FSTTCS.2020.8
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 â^S3. For k-center and k-means problems, our algorithms also achieve polynomial dependence on the number of clusters, k, when Î± â¥ 2 â^S3 Îµ 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 â^S3 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.
关键词：clustering; stability; local search; dynamic programming; coreset; polyhedral metric; trapezoid decomposition; range query