2015/07/08 by Sayan Bandyapadhyay, Bandyapadhyay, Sayan, Kasturi Varadarajan +1 · 1 citation
Computer Science · Mathematics · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.CG #cs.DS #math.PR
paper · pdf · doi:10.48550/arxiv.1507.02222
19 pages
arxiv created 2016/10/03 · arxiv updated 2016/10/05
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 ∪ Y. We would like to cover the clients by balls centered at the servers. The objective function to minimize is the sum of the α-th power of the radii of the balls. Here α≥ 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α and a cα 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 α 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 α≥ log |X|.