Conference proceeding
Approximate Clustering via Metric Partitioning
Leibniz International Proceedings in Informatics, LIPIcs, Vol.64, pp.15.1-15.13
07/08/2015
DOI: 10.4230/lipics.isaac.2016.15
Abstract
In this paper we consider two metric covering/clustering problems - \textit{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|$.
Details
- Title: Subtitle
- Approximate Clustering via Metric Partitioning
- Creators
- Sayan Bandyapadhyay - University of IowaKasturi Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Leibniz International Proceedings in Informatics, LIPIcs, Vol.64, pp.15.1-15.13
- Publisher
- Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
- DOI
- 10.4230/lipics.isaac.2016.15
- ISSN
- 1868-8969
- Grant note
- 1318996 / National Science Foundation (nsf_________::NSF)
- Language
- English
- Date published
- 07/08/2015
- Academic Unit
- Computer Science
- Record Identifier
- 9984259500502771
Metrics
10 Record Views