Abstract
In this paper we consider two metric covering/clustering problems  Minimum Cost Covering Problem (MCC) and kclustering. 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 alphath 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 kclustering problem. The main difference between kclustering and MCC is that in kclustering one needs to select k balls to cover the clients.
For any eps > 0, we describe quasipolynomial time (1 + eps) approximation algorithms for both of the problems. However, in case of kclustering the algorithm uses (1 + eps)k balls. Prior to our work, a 3^alpha and a c^alpha approximation were achieved by polynomialtime algorithms for MCC and kclustering, 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 kclustering), if one is willing to settle for quasipolynomial 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:115:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6775},
URN = {urn:nbn:de:0030drops67751},
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 