A (3 + ɛ)-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds

Clustering is a fundamental problem setting with applications in many different areas. For a given set of points in a metric space and an integer k, we seek to partition the given points into k clusters. For each computed cluster, one typically defines one point as the center of the cluster. A natural objective is to minimize the sum of the cluster center's radii, where we assign the smallest radius r to each center such that each point in the cluster is at a distance of at most r from the center. The best-known polynomial time approximation ratio for this problem is 3.389. In the setting with outliers, i.e., we are given an integer m and allow up to m points that are not in any cluster, the best-known approximation factor is 12.365.

In this paper, we improve both approximation ratios to 3 + ǫ. Our algorithms are primaldual algorithms that use fundamentally new ideas to compute solutions and to guarantee the claimed approximation ratios.

For example, we replace the classical binary search to find the best value of a Lagrangian multiplier λ by a primal-dual routine in which λ is a variable that is raised. Also, we show that for each connected component due to almost tight dual constraints, we can find one single cluster that covers all its points and we bound its cost via a new primal-dual analysis. We remark that our approximation factor of 3 + ǫ is a natural limit for the known approaches in the literature.

Then, we extend our results to the setting of lower bounds. There are algorithms known for the case that for each point i there is a lower bound Li, stating that we need to assign at least Li clients to i if i is a cluster center. For this setting, there is a 3.83 approximation if outliers are not allowed and a 12.365-approximation with outliers. We improve both ratios to 3.5 + ǫ and, at the same time, generalize the type of allowed lower bounds.