Distributed k-Clustering for Data with Heavy Noise
In this paper, we consider the k-center/median/means clustering with outliers problems (or the (k, z)-center/median/means problems) in the distributed setting. Most previous distributed algorithms have their communication costs linearly depending on z, the number of outliers. Recently Guha et al. [10] overcame this dependence issue by considering bi-criteria approximation algorithms that output solutions with 2z outliers. For the case where z is large, the extra z outliers discarded by the algorithms might be too large, considering that the data gathering process might be costly. In this paper, we improve the number of outliers to the best possible (1 + )z, while maintaining the O(1)-approximation ratio and independence of communication cost on z. The problems we consider include the (k, z)-center problem, and (k, z)-median/means problems in Euclidean metrics. Implementation of the our algorithm for (k, z)-center shows that it outperforms many previous algorithms, both in terms of the communication cost and quality of the output solution.
The paper describes algorithms for distributed k-center/k-median/k-means clustering. For distributed k-center, it is known that any constant approximation needs Omega(z) communication cost, where z is the number of allowed outliers. This can be avoided by using a bicriteria approximation where more than z outliers are allowed, but the cost is compared to the best solution with at most z outliers. It is known that using 2z outliers is sufficient to obtain a O(1)-approximation. The paper at hand now improves the violation with respect to the number of outliers to (1+eps)*z. The result is given for metric k-center, but works for Euclidean k-center as well (since Euclidean distances are a metric, and only O(1) is obtained anyway).  For Euclidean k-median/k-means, a similar result is obtained using coresets. However, here the interpretation is a bit different, since these problems can (under no assumptions on n and d) not be (1+eps)-approximated. (This still needs to be done by the coordinator after collecting the information). Nevertheless, coresets have proven useful for plain k-median/k-means as well, so I consider this extension to be meaningful.  The paper is well written and contains a helpful figure for understanding the main proof. The algorithm is elegant.   The experiments have not made it into the actual paper, which I think is not so good. The experiments do look solid and compare several approaches. I hope that a long version of this paper is going to be published soon after the publication of the conference version so that this part of the paper is not lost to the reader. The one-sentence summary of it in the actual conference version is not very informative.  The overall accessment probably hinges on the question how important the improvement from 2z to (1+eps)z is.   - The sentence on [5] in line 114 should have k-median in it and not k-center. - To the conclusion: It seems unlikely that the problem can be solved within a 1+eps factor on the coreset for k-median/k-means, since the problems are even APX-hard without the outlier part.  Edit after rebuttal: Since I cannot pinpoint an exact minus point for this paper and the result is interesting, I've update my score to accept.