Abstract: Hard-capacitated $k$-means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and data mining areas. In this problem, one is required to partition a given $n$-point set into $k$ disjoint clusters with known capacity so as to minimize the sum of within-cluster variances. It is known to be at least APX-hard and for which most of the work is from a meta heuristic perspective. To the best our knowledge, no constant approximation algorithm or existence proof of such an algorithm is known. As our main contribution, we propose an FPT($k$) algorithm with performance guarantee of $69+\epsilon$ for any HCKM instances in this paper.
Introduction: The Challenge of Capacitated Clustering
Clustering is a cornerstone of data science, and $k$-means is its most famous variant. In standard $k$-means, we partition $n$ points into $k$ clusters to minimize the sum of squared distances to cluster centers. However, real-world applications—like logistics, facility location, or school zoning—often involve capacities: each cluster can only hold a maximum number of points ($u$).
This "hard-capacitated" constraint (HCKM) makes the problem significantly harder. In standard $k$-means, once you pick centers, you simply assign every point to its nearest center (the Voronoi partition). In HCKM, a point might be forced to a distant center because its nearest center is "full." This breaks the geometric structure of the problem, making it APX-hard and leaving researchers with only heuristics or "pseudo-approximations" until now.
Methodology
The authors propose a multi-step approach that combines geometric approximation with Fixed-Parameter Tractability (FPT). The algorithm bypasses the structural complexities that have historically made this problem resistant to constant-ratio guarantees.
1. Bi-criteria Coarsening
The process begins by running a known bi-criteria $k$-means algorithm (such as Hsu’s algorithm) to find a "representing set" $S$ of $O(k)$ points. This set effectively summarizes the geometry of the dataset, reducing the complexity of the search space.
2. A Novel Metric ($\mathbb{H}$)
The authors define a new distance metric, $h(x, y)$, which measures the distance between points by "routing" them through the nearest points in the representing set $S$. This simplification is key to managing the search space for optimal centers.
3. FPT Brute Force and Linear Programming
Since the number of clusters $k$ is typically small compared to the number of points $n$, the authors use a brute-force approach to "guess" the distribution of the $k$ centers across the $O(k)$ regions defined by the representing set. Once the centers are fixed, the problem of assigning points to those centers while respecting capacities becomes a transportation problem. The authors demonstrate that the Linear Programming (LP) relaxation for this assignment is "totally unimodular," ensuring integer solutions and allowing for an exact, polynomial-time assignment.
Key Insights and Theoretical Results
The most significant contribution is the Metric Transformation. By proving that the cost in the new metric $\mathbb{H}$ is bounded relative to the standard Euclidean metric $\mathbb{D}$, the authors can solve the problem in a discrete space ($S$) while maintaining a guarantee for the original problem. This approach effectively bypasses the "Voronoi breakdown" inherent in capacitated problems.
Performance Guarantees
- Approximation Ratio: The algorithm achieves a performance guarantee of $69 + \epsilon$. This is the first known constant-factor approximation for HCKM.
- Computational Complexity: The algorithm is Fixed-Parameter Tractable with a running time of $2^{O(k \log k)} n^{O(1)}$. This confirms that for a fixed $k$, the problem is solvable in polynomial time relative to the number of data points.
Discussion and Future Work
While a "constant" approximation is a massive theoretical win, the value 69 is relatively high for practical use. The authors acknowledge their analysis is aimed at proving the existence of a constant ratio. Future work may focus on:
- Optimizing the Constant: Reducing the $69$ factor to a more practical value.
- Non-uniform Capacities: Extending the model to handle varying capacities across clusters.
- True Polynomial Time: Moving from an FPT algorithm to a true polynomial-time approximation algorithm where the exponent of $n$ is independent of $k$.
This work provides a foundational proof that constant-factor approximations are possible for hard-capacitated $k$-means, opening new avenues for both theoretical research and practical algorithm design in constrained clustering.
Summary updated