Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median

We consider two closely related fundamental clustering problems in this paper. In Min-Sumk-Clustering, one is given n points in a metric space and has to partition them into k clusters while minimizing the sum of pairwise distances between points in the same cluster. In the Balancedk-Median problem, the instance is the same and the objective is to obtain a partitioning into k clusters $C_1,\dots ,C_k$, where each cluster $C_i$ is centered at a point $c_i$, while minimizing the total assignment cost of the points in the metric; the cost of assigning a point j to a cluster $C_i$ is equal to $|C_i|$ times the distance between j and $c_i$ in the metric. In this article, we present an $O(\log n)$-approximation for both these problems. This is an improvement over the $O({ϵ}^{-1}{\log }^{1+ϵ}n)$-approximation (for any constant $ϵ>0$) obtained by Bartal, Charikar, and Raz [STOC '01]. We also obtain a quasi-PTAS for Balanced k-Median in metrics with constant doubling dimension. As in the work of Bartal et al., our approximation for general metrics uses embeddings into tree metrics. The main technical contribution in this paper is an O(1)-approximation for Balanced k-Median in hierarchically separated trees (HSTs). Our improvement comes from a more direct dynamic programming approach that heavily exploits the properties of standard HSTs. In this way, we avoid the reduction to special types of HSTs that were considered by Bartal et al., thereby avoiding an additional $O({ϵ}^{-1}{\log }^{ϵ}n)$ loss.