DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2019.40

Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction

Authors: Hu Ding, Haikuo Yu, and Zixiu Wang

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract

We study the problem of k-center clustering with outliers in arbitrary metrics and Euclidean space. Though a number of methods have been developed in the past decades, it is still quite challenging to design quality guaranteed algorithm with low complexity for this problem. Our idea is inspired by the greedy method, Gonzalez’s algorithm, for solving the problem of ordinary k-center clustering. Based on some novel observations, we show that this greedy strategy actually can handle k-center clustering with outliers efficiently, in terms of clustering quality and time complexity. We further show that the greedy approach yields small coreset for the problem in doubling metrics, so as to reduce the time complexity significantly. Our algorithms are easy to implement in practice. We test our method on both synthetic and real datasets. The experimental results suggest that our algorithms can achieve near optimal solutions and yield lower running times comparing with existing methods.

Cite as

Hu Ding, Haikuo Yu, and Zixiu Wang. Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ding_et_al:LIPIcs.ESA.2019.40,
  author =	{Ding, Hu and Yu, Haikuo and Wang, Zixiu},
  title =	{{Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.40},
  URN =		{urn:nbn:de:0030-drops-111613},
  doi =		{10.4230/LIPIcs.ESA.2019.40},
  annote =	{Keywords: k-center clustering, outliers, coreset, doubling metrics, random sampling}
}

Search Results

Documents authored by Yu, Haikuo

Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction

Abstract

Cite as

Thanks for your feedback!

Could not send message