A constant FPT approximation algorithm for hard-capacitated k-means

Yicheng Xu, Rolf H. Möhring, Dachuan Xu, Yong Zhang, Yifei Zou

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.

Figure 1: A visualization of the hard-capacitated k-means problem structure, where points are assigned to centers within partitioned regions.

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.

Figure 2: Illustration of the metric transformation h(x, y) involving routing through representative 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

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+ε$ for any HCKM instances in this paper.
BibTeX
@inproceedings{xu2020constant,
  author = {Yicheng Xu and Rolf H. Möhring and Dachuan Xu and Yong Zhang and Yifei Zou},
  title = {{A constant FPT approximation algorithm for hard-capacitated k-means}},
  booktitle = {Optimization},
  year = {2020},
  doi = {10.1007/s11081-020-09503-0},
}
Figure