Balanced $k$-Center Clustering When $k$ Is A Constant

Abstract

The problem of constrained $k$-center clustering has attracted significant attention in the past decades. In this paper, we study balanced $k$-center cluster where the size of each cluster is constrained by the given lower and upper bounds. The problem is motivated by the applications in processing and analyzing large-scale data in high dimension. We provide a simple nearly linear time $4$-approximation algorithm when the number of clusters $k$ is assumed to be a constant. Comparing with existing method, our algorithm improves the approximation ratio and significantly reduces the time complexity. Moreover, our result can be easily extended to any metric space.

References in corpus (4)

• Fast Clustering with Lower Bounds: No Customer too Far, No Shop too Small
• Constant Factor Approximation for Capacitated k-Center with Outliers
• Capacitated Center Problems with Two-Sided Bounds and Outliers
• Data Driven Resource Allocation for Distributed Learning

Cited by in corpus (1)

• Faster Balanced Clusterings in High Dimension