An Improved Greedy Approximation for (Metric) k-Means

Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Le, Ernest van Wijland2025 · DOI

TL;DR

This paper presents a new greedy approximation algorithm for the k-Means clustering problem that achieves a $3+2\sqrt{2}+\varepsilon \approx 5.83$ approximation factor for general metric spaces. This significantly improves upon previous best-known approximations and even slightly surpasses the state-of-the-art for the Euclidean case. The core innovation lies in adapting a powerful Lagrangian Multiplier Preserving (LMP) technique, typically used for facility location with linear costs, to handle squared distances, which are crucial for k-Means.

What Problem Does This Paper Address?

The k-Means problem is a fundamental task in data analysis and machine learning. Given a set of data points and an integer $k$, the goal is to partition the points into $k$ clusters, each represented by a center, such that the sum of squared distances from each point to its assigned cluster center is minimized. While the problem is NP-hard, significant research has focused on developing approximation algorithms. The challenge has been to find algorithms that provide a good approximation guarantee (meaning the cost of the found solution is close to the optimal cost) in polynomial time. Previous work achieved a $(9+\varepsilon)$-approximation for general metric spaces and a $5.92$-approximation for the Euclidean case. A key hurdle in improving these bounds was adapting existing approximation techniques, particularly those based on Lagrangian Multiplier Preserving (LMP) methods for the related facility location problem, to the squared distance metric used in k-Means. Squared distances violate the triangle inequality, making direct application of existing LMP algorithms problematic.

Methods

The paper's main contribution is a novel adaptation of a greedy LMP algorithm for facility location to handle squared metric connection costs. This is achieved by carefully modifying the bidding strategy of clients and the analysis of the algorithm. The authors introduce a new bidding mechanism that involves a parameter $\gamma = 1+\sqrt{2}$ and a specific update rule for client bids. This adapted LMP algorithm provides a $(3+2\sqrt{2})$-approximation for the facility location problem with squared costs.

This LMP algorithm is then combined with a framework recently developed for the k-Median problem. This framework involves using two different approximation algorithms and a "walking between solutions" technique to merge them. One algorithm provides a bicriteria approximation (allowing more than $k$ centers), and the other works for "stable" instances. By carefully combining these, the authors achieve the final $3+2\sqrt{2}+\varepsilon$ approximation for k-Means. The paper details complex procedures like "MergeSolutions" and "LogAdaptiveAlgorithm" to manage the merging of solutions and adapt to different phases of the algorithm, ensuring the desired approximation guarantee.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and analysis for general metric spaces, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Adapting LMP for Squared Distances: The core insight is overcoming the challenge of applying LMP techniques, which are typically linear, to squared distances. This required a novel modification of the bidding strategy and a more robust analysis to handle the violation of the triangle inequality for squared distances.
  • Leveraging Facility Location for k-Means: The paper demonstrates a powerful connection between the facility location problem and k-Means, showing that improvements in facility location approximation can directly translate to better k-Means approximations.
  • "Walking Between Solutions" for Improved Guarantees: The strategy of combining multiple approximation algorithms and merging their solutions is a key technique for achieving better overall approximation ratios, especially when dealing with specific instance properties like "stability."
  • The Importance of "Robustness" in Analysis: The paper introduces a more robust analysis framework that handles "n-openable" facilities and "n-valid" sequences, which is crucial for the correctness of the merging procedure.

Key Results

  • A polynomial-time $(3+2\sqrt{2}+\varepsilon)$-approximation algorithm for the general metric k-Means problem. This is a significant improvement over the previous $(9+\varepsilon)$-approximation.
  • This result also slightly improves upon the best known approximation for the Euclidean k-Means problem, achieving $3+2\sqrt{2}+\varepsilon \approx 5.83$ compared to the previous $5.92$.
  • The paper introduces a novel greedy LMP algorithm for facility location with squared metric connection costs, achieving a $(3+2\sqrt{2})$-approximation.

Limitations and Future Work

  • Complexity of the Algorithm: The paper acknowledges that the detailed analysis and algorithms are "rather technical" and involve complex procedures like "MergeSolutions" and "LogAdaptiveAlgorithm." While polynomial-time, the practical implementation might be challenging due to the numerous steps and parameters.
  • Constant Factors: The authors mention that they have not optimized the constant factors in their analysis, suggesting that further improvements might be possible.
  • Future Work: The paper's techniques, particularly the adapted LMP algorithm and the merging framework, are expected to be applicable to other related clustering problems, such as k-Median and k-Center, potentially leading to further algorithmic advancements in these areas.

Summary updated

Abstract

Clustering is a basic task in data analysis and machine learning, and the optimization of clustering objectives are well-studied optimization problems; amongst these, the k Means objective is arguably the most well known. Given a collection of points in a metric space, the goal is to partition them into k clusters, each with an associated center, so as to minimize the sum of squared distances of points to their cluster centers. In this paper, we present a polynomial-time $3+2 \sqrt{2}+\varepsilon{\lt}5.83$-approximation algorithm for k-Means in general metrics. This substantially improves on the current-best $(9+\varepsilon)$-approximation in [Ahmadian, Norouzi-Fard, Svensson, Ward - FOCS’17, SICOMP’20], and even slightly improves on the 5.92-approximation in [Cohen-Addad, Esfandiari, Mirrokni, Narayanan - STOC’22] for the Euclidean special case. A natural approach for k-Means is to leverage Lagrangian Multiplier Preserving (LMP) approximations for the facility location problem. The previous best results for k-Means build upon an adaptation of an LMP 3-approximation for facility location with metric connection costs in [Jain, Vazirani J.ACM’01] based on a primal-dual method, rather than on the improved LMP greedy 2-approximation for the same problem in [Jain, Mahdian, Markakis, Saberi, Vazirani - J.ACM’03]. The barrier to using the improved LMP algorithm was that no adaptation of this algorithm and its analysis to the case of squared metric connection costs was known (since squared distances violate triangle inequality). Our main contribution is overcoming this barrier by providing such an adaptation. This new LMP approximation algorithm is then combined with the framework recently introduced in [Cohen-Addad, Grandoni, Lee, Schwiegelshohn, Svensson - STOC’25] for the related (metric) k Median problem.
BibTeX
@misc{charikar2025improved,
  author = {Moses Charikar and Vincent Cohen-Addad and Ruiquan Gao and Fabrizio Grandoni and Euiwoong Le and Ernest van Wijland},
  title = {{An Improved Greedy Approximation for (Metric) k-Means}},
  year = {2025},
  doi = {10.1109/focs63196.2025.00016},
}
Figure