1 Search Results for "Yu, Haikuo"


Document
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-dev.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}
}
  • Refine by Author
  • 1 Ding, Hu
  • 1 Wang, Zixiu
  • 1 Yu, Haikuo

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 1 coreset
  • 1 doubling metrics
  • 1 k-center clustering
  • 1 outliers
  • 1 random sampling

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail