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.ISAAC.2016.15
URN: urn:nbn:de:0030-drops-67751
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6775/
Go to the corresponding LIPIcs Volume Portal

Bandyapadhyay, Sayan ; Varadarajan, Kasturi

Approximate Clustering via Metric Partitioning

pdf-format:
LIPIcs-ISAAC-2016-15.pdf (0.5 MB)

Abstract

In this paper we consider two metric covering/clustering problems - Minimum Cost Covering Problem (MCC) and k-clustering. In the MCC problem, we are given two point sets X (clients) and Y (servers), and a metric on X cup Y. We would like to cover the clients by balls centered at the servers. The objective function to minimize is the sum of the alpha-th power of the radii of the balls. Here alpha geq 1 is a parameter of the problem (but not of a problem instance). MCC is closely related to the k-clustering problem. The main difference between k-clustering and MCC is that in k-clustering one needs to select k balls to cover the clients.

For any eps > 0, we describe quasi-polynomial time (1 + eps) approximation algorithms for both of the problems. However, in case of k-clustering the algorithm uses (1 + eps)k balls. Prior to our work, a 3^alpha and a c^alpha approximation were achieved by polynomial-time algorithms for MCC and k-clustering, respectively, where c > 1 is an absolute constant. These two problems are thus interesting examples of metric covering/clustering problems that admit (1 + eps)-approximation (using (1 + eps)k balls in case of k-clustering), if one is willing to settle for quasi-polynomial time. In contrast, for the variant of MCC where alpha is part of the input, we show under standard assumptions that no polynomial time algorithm can achieve an approximation factor better than O(log |X|) for alpha geq log |X|.

BibTeX - Entry

@InProceedings{bandyapadhyay_et_al:LIPIcs:2016:6775,
  author =	{Sayan Bandyapadhyay and Kasturi Varadarajan},
  title =	{{Approximate Clustering via Metric Partitioning}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6775},
  URN =		{urn:nbn:de:0030-drops-67751},
  doi =		{10.4230/LIPIcs.ISAAC.2016.15},
  annote =	{Keywords: Approximation Algorithms, Clustering, Covering, Probabilistic Parti- tions}
}

Keywords: Approximation Algorithms, Clustering, Covering, Probabilistic Parti- tions
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

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