ECCC-Report TR11-015https://eccc.weizmann.ac.il/report/2011/015Comments and Revisions published for TR11-015en-usMon, 07 Feb 2011 10:51:50 +0200
Paper TR11-015
| Hardness and Non-Approximability of Bregman Clustering Problems |
Marcel R. Ackermann,
Johannes BlĂ¶mer,
Christoph Scholz
https://eccc.weizmann.ac.il/report/2011/015We prove the computational hardness of three k-clustering problems using an (almost) arbitrary Bregman divergence as dissimilarity measure: (a) The Bregman k-center problem, where the objective is to find a set of centers that minimizes the maximum dissimilarity of any input point towards its closest center, and (b) the Bregman k-diameter problem, where the objective is to minimize the maximum dissimilarity between pairs of points from the same cluster, and (c) the Bregman k-median problem, where the objective is to find a set of centers that minimizes the average dissimilarity of any input point towards its closest center. We show that solving these problems is NP-hard, and that it is even NP-hard to approximate a solution of (a) and (b) within a factor of (a) 3.32 and (b) 3.87, respectively. To obtain our results, we give a gap-preserving reduction from the Euclidean k-center (k-diameter, k-means) problem to the Bregman k-center (k-diameter, k-median) problem. This reduction combines the technique of Mahalanobis-similarity from Ackermann et al. (SODA '08) with a reduction already used by Chaudhuri and McGregor (COLT '08) to show the non-approximability of the Kullback-Leibler k-center problem, and a recent reduction given by Vattani to prove the NP-hardness of the Euclidean k-means problem.Mon, 07 Feb 2011 10:51:50 +0200https://eccc.weizmann.ac.il/report/2011/015