License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.8
URN: urn:nbn:de:0030-drops-132492
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13249/
Go to the corresponding LIPIcs Volume Portal

Agarwal, Pankaj K. ; Chang, Hsien-Chih ; Munagala, Kamesh ; Taylor, Erin ; Welzl, Emo

Clustering Under Perturbation Stability in Near-Linear Time

pdf-format:
LIPIcs-FSTTCS-2020-8.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{agarwal_et_al:LIPIcs:2020:13249,
  author =	{Pankaj K. Agarwal and Hsien-Chih Chang and Kamesh Munagala and Erin Taylor and Emo Welzl},
  title =	{{Clustering Under Perturbation Stability in Near-Linear Time}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Nitin Saxena and Sunil Simon},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13249},
  URN =		{urn:nbn:de:0030-drops-132492},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.8},
  annote =	{Keywords: clustering, stability, local search, dynamic programming, coreset, polyhedral metric, trapezoid decomposition, range query}
}

Keywords: clustering, stability, local search, dynamic programming, coreset, polyhedral metric, trapezoid decomposition, range query
Collection: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI