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

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

This paper, titled "A constant FPT approximation algorithm for hard-capacitated k-means," presents a significant theoretical breakthrough in the field of combinatorial optimization. The authors provide the first known constant-factor approximation algorithm for the hard-capacitated version of the classic $k$-means clustering problem.

TL;DR

The authors propose the first constant-factor approximation algorithm ($69 + \epsilon$) for the hard-capacitated $k$-means problem. By leveraging Fixed-Parameter Tractability (FPT) with respect to the number of clusters $k$, they bypass the structural complexities that have historically made this problem resistant to constant-ratio guarantees.

What Problem Does This Paper Address?

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" (which violate capacities to get a solution) until now.

Methods

The authors use a multi-step approach that combines geometric approximation with Fixed-Parameter Tractability (FPT):

  1. Bi-criteria Coarsening: They first run a known bi-criteria $k$-means algorithm (like Hsu’s algorithm) to find a "representing set" $S$ of $O(k)$ points. This set effectively summarizes the geometry of the dataset.
  2. A Novel Metric ($\mathbb{H}$): They 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 simplifies the search space for optimal centers.
  3. FPT Brute Force: 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.
  4. Linear Programming for Assignment: Once the centers are fixed (based on the "guess"), the problem of assigning points to those centers while respecting capacities becomes a transportation problem. The authors show that the Linear Programming (LP) relaxation for this assignment is "totally unimodular," meaning the LP naturally produces integer solutions, allowing for an exact, polynomial-time assignment.

Datasets

This is a theoretical paper focused on algorithmic proofs and complexity analysis. Consequently, no empirical datasets were used for evaluation. The results are proven to hold for any general HCKM instance in $d$-dimensional Euclidean space.

Key Insights and Ideas

  • Metric Transformation: The most clever move is the introduction of metric $\mathbb{H}$. By proving that the cost in this new metric is bounded relative to the standard Euclidean metric $\mathbb{D}$, the authors can solve the problem in a discrete, manageable space ($S$) and still provide a guarantee for the original problem.
  • Bypassing the Voronoi Breakdown: The authors recognize that while the Voronoi property is lost in HCKM, the "optimal" centers must still be "near" the data. By using the representing set $S$, they restrict the search for centers to a set of size $O(k)$ rather than the infinite Euclidean space or the $n$ data points.
  • The Power of FPT: The paper demonstrates that while HCKM is intractable in the general sense, it becomes solvable if we are willing to accept a runtime that is exponential in $k$ but polynomial in $n$. This is a practical trade-off for many real-world datasets where $k$ is small (e.g., $k < 20$).

Key Results

  • Approximation Ratio: The algorithm achieves a performance guarantee of $69 + \epsilon$. This means the solution found will never be more than roughly 69 times worse than the absolute theoretical optimum.
  • 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 can be solved in polynomial time relative to the number of data points.
  • Integrality: The paper proves that the assignment sub-problem (given fixed centers) can be solved exactly in polynomial time because the underlying constraint matrix is totally unimodular.

Limitations and Future Work

  • The Constant Factor: While a "constant" approximation is a massive theoretical win, the value 69 is quite high for practical use. The authors acknowledge their analysis is "rough" and aimed at proving the existence of a constant ratio rather than optimizing it.
  • Exponential Dependence on $k$: Because the runtime is exponential in $k$, the algorithm becomes computationally expensive as the number of clusters grows.
  • Non-uniform Capacities: The current model assumes a uniform capacity $u$ for all clusters. The authors suggest that extending this to non-uniform capacities is a promising direction for future research.
  • Faster Algorithms: Moving from an FPT algorithm to a true polynomial-time approximation algorithm (where the exponent of $n$ does not depend on $k$) remains an open challenge.

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},
}

Loading related content...

Figure