1 Search Results for "Banerjee, Sandip"


Document
APPROX
Min-Sum Clustering (With Outliers)

Authors: Sandip Banerjee, Rafail Ostrovsky, and Yuval Rabani

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)


Abstract
We give a constant factor polynomial time pseudo-approximation algorithm for min-sum clustering with or without outliers. The algorithm is allowed to exclude an arbitrarily small constant fraction of the points. For instance, we show how to compute a solution that clusters 98% of the input data points and pays no more than a constant factor times the optimal solution that clusters 99% of the input data points. More generally, we give the following bicriteria approximation: For any ε > 0, for any instance with n input points and for any positive integer n' ≤ n, we compute in polynomial time a clustering of at least (1-ε) n' points of cost at most a constant factor greater than the optimal cost of clustering n' points. The approximation guarantee grows with 1/(ε). Our results apply to instances of points in real space endowed with squared Euclidean distance, as well as to points in a metric space, where the number of clusters, and also the dimension if relevant, is arbitrary (part of the input, not an absolute constant).

Cite as

Sandip Banerjee, Rafail Ostrovsky, and Yuval Rabani. Min-Sum Clustering (With Outliers). In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 16:1-16:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{banerjee_et_al:LIPIcs.APPROX/RANDOM.2021.16,
  author =	{Banerjee, Sandip and Ostrovsky, Rafail and Rabani, Yuval},
  title =	{{Min-Sum Clustering (With Outliers)}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.16},
  URN =		{urn:nbn:de:0030-drops-147093},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.16},
  annote =	{Keywords: Clustering, approximation algorithms, primal-dual}
}
  • Refine by Author
  • 1 Banerjee, Sandip
  • 1 Ostrovsky, Rafail
  • 1 Rabani, Yuval

  • Refine by Classification
  • 1 Theory of computation → Facility location and clustering

  • Refine by Keyword
  • 1 Clustering
  • 1 approximation algorithms
  • 1 primal-dual

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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