Source-linked AI summary
The Hardness of Approximation of Euclidean k-means
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop
TL;DR
Euclidean k-means had limited hardness evidence despite extensive approximation results, leaving open whether a PTAS exists for arbitrary k and d. The paper reduces triangle-free Vertex Cover to Euclidean k-means and proves the first constant-factor inapproximability result, while also establishing corresponding triangle-free Vertex Cover hardness.
Problem
Euclidean k-means had remained understood only up to NP-hardness, leaving open whether a PTAS exists for arbitrary k and d.
Method
The paper efficiently reduces Vertex Cover on triangle-free graphs to Euclidean k-means and transfers Vertex Cover hardness to triangle-free graphs.
Results
There exists a constant ε > 0 such that approximating Euclidean k-means within a factor better than (1 + ε) is NP-hard.
Takeaways & Limitations
The paper provides the first hardness of approximation for Euclidean k-means and establishes triangle-free Vertex Cover hardness within any factor smaller than 1.36.
Takeaways & Limitations
The reduction produces high-dimensional instances, and constant-dimensional inapproximability remains an open question.
Abstract
from arXiv · showhide
The Euclidean $k$-means problem is a classical problem that has been extensively studied in the theoretical computer science, machine learning and the computational geometry communities. In this problem, we are given a set of $n$ points in Euclidean space $R^d$, and the goal is to choose $k$ centers in $R^d$ so that the sum of squared distances of each point to its nearest center is minimized. The best approximation algorithms for this problem include a polynomial time constant factor approximation for general $k$ and a $(1+ε)$-approximation which runs in time $poly(n) 2^{O(k/ε)}$. At the other extreme, the only known computational complexity result for this problem is NP-hardness [ADHP'09]. The main difficulty in obtaining hardness results stems from the Euclidean nature of the problem, and the fact that any point in $R^d$ can be a potential center. This gap in understanding left open the intriguing possibility that the problem might admit a PTAS for all $k,d$. In this paper we provide the first hardness of approximation for the Euclidean $k$-means problem. Concretely, we show that there exists a constant $ε> 0$ such that it is NP-hard to approximate the $k$-means objective to within a factor of $(1+ε)$. We show this via an efficient reduction from the vertex cover problem on triangle-free graphs: given a triangle-free graph, the goal is to choose the fewest number of vertices which are incident on all the edges. Additionally, we give a proof that the current best hardness results for vertex cover can be carried over to triangle-free graphs. To show this we transform $G$, a known hard vertex cover instance, by taking a graph product with a suitably chosen graph $H$, and showing that the size of the (normalized) maximum independent set is almost exactly preserved in the product graph using a spectral analysis, which might be of independent interest.
1 Introduction
Euclidean k-means seeks provable approximations for clustering points in Euclidean space, but its approximability remained poorly understood. The paper answers the open PTAS question negatively with the first constant-factor hardness result and related triangle-free Vertex Cover hardness.
- Euclidean k-means chooses k centers for n points in R^d to minimize each point’s squared distance to its nearest center.
- The k-means heuristic can converge to solutions far from the optimum, motivating provable algorithms for general Euclidean instances.
- For arbitrary k and d, the best known approximation achieves a factor of 9 + ε, while lower bounds had remained elusive beyond NP-hardness.
- The paper shows that no PTAS exists for arbitrary k and d unless P = NP, by proving constant-factor hardness for Euclidean k-means.
- There exists a constant ε > 0 such that approximating Euclidean k-means within a factor better than (1 + ε) is NP-hard.
- The reduction starts from Vertex Cover on triangle-free graphs, whose hardness is also established within any factor smaller than 1.36.
2 Main Technical Contribution
The technical contribution reduces Vertex Cover on triangle-free graphs to Euclidean k-means and connects low clustering cost with small vertex covers. It also transfers known Vertex Cover hardness to triangle-free graphs.
- The reduction maps triangle-free Vertex Cover instances to Euclidean k-means instances where small covers correspond to low clustering cost.
- The analysis relates cluster costs to structural properties of the original graph, converting the Euclidean objective into a combinatorial problem.
- Known Vertex Cover hardness results are shown to carry over to triangle-free graphs.
3 Related Work
Prior work provides strong approximation algorithms and fixed-parameter PTAS results for k-means, while related clustering objectives have different center and metric restrictions. The paper’s hardness result addresses a comparatively open lower-bound landscape.
- Euclidean k-means: k-means++ achieves an O(log k)-factor approximation, while local search improves the best general approximation to 9 + ε.
- Euclidean k-means: For fixed k, PTAS results obtain efficient schemes with exponential dependence on k and improved dependence on n and d.
- Euclidean k-means: Euclidean k-means is NP-hard even for k = 2, and hardness also holds for points in the plane.
- Related objectives: k-median minimizes unsquared distances and typically restricts centers to data points or an input-specified candidate set, unlike Euclidean k-means.
- Related objectives: For k-center, the objective minimizes the maximum distance to a center; in Euclidean space its best known hardness factor is 1.82.
4 Our Hardness Reduction: From Vertex Cover to Euclidean k-means
The reduction encodes triangle-free Vertex Cover instances as Euclidean k-means instances, making low clustering cost correspond to small vertex covers. Completeness and soundness together yield an approximation-preserving hardness result.
- Reduction construction: The reduction maps triangle-free Vertex Cover instances efficiently to Euclidean k-means instances.The constructed k-means points correspond to graph edges, using vectors formed from endpoint unit vectors.
- Completeness: A vertex cover of size k yields a k-means clustering with cost at most m − k.Edges assigned to cover vertices form clusters whose costs sum to one less than their edge counts.
- Soundness: If the Vertex Cover optimum is at least k(1 + ǫ), the corresponding optimal k-means cost is bounded below by the reduction’s soundness guarantee.The displayed lower-bound expression is truncated in the supplied passage, but the reduction uses it to separate the two cases.
- Hardness consequence: For hard instances with m = Θ(n) edges and k = Ω(n), the reduction distinguishes cover size k from at least (1 + ǫ)k.Choosing k proportional to m converts this gap into a constant-factor k-means hardness result.
- Dimension: The construction initially uses n-dimensional vectors, but Johnson–Lindenstrauss reduction preserves the hardness in O(log n/ǫ^2) dimensions.The paper retains n dimensions for simpler exposition.
- Soundness: Low k-means cost implies a vertex cover of size (1 + O(δ))k, because most low-cost clusters must be stars.Triangle-freeness rules out the alternative triangle structure, allowing cluster centers to cover the relevant edges.
5 Hardness of Vertex Cover on Triangle-Free Graphs
The paper transfers vertex-cover hardness to triangle-free graphs using graph products and spectral analysis, preserving normalized independent-set size up to the required approximation factor. This yields NP-hardness of approximating vertex cover within any factor smaller than 1.36 on bounded-degree triangle-free graphs.
- Hardness transfer: Independent sets and vertex covers are complementary: IS(G) + VC(G) = |V|.This duality transfers approximation information between independent set and vertex cover.
- Graph-product reduction: The normalized maximum independent-set size of the product graph is preserved within a factor of 1+ε.The construction uses a polynomial-size, bounded-degree graph product whose parameters depend polynomially on Δ and ε^-1.
- Hardness transfer: The construction is polynomial-time and produces triangle-free graphs with polynomially bounded size and degree.Theorem 14 specifies poly(Δ, ε^-1)|V| nodes and polynomial degree in the resulting graph.
- Hardness consequence: 1.36 is the resulting unconditional hardness threshold for vertex cover on bounded-degree triangle-free graphs.This follows by combining the approximation-preserving reduction with the known hardness result for general bounded-degree graphs.
- Graph-product reduction: The reduction transforms a graph G into a triangle-free graph using a graph product with a suitably chosen regular graph H.The product preserves triangle-freeness when H is triangle-free and uses spectral properties of H to control independent sets.
6 Conclusions
The paper establishes the first hardness of approximation for Euclidean k-means, but leaves a substantial gap between this result and the best known upper bound. It also identifies dimensionality and extensions to related problems as open directions.
- Main conclusion: The paper provides the first hardness of approximation for the fundamental Euclidean k-means problem.This goes beyond the previously known NP-hardness result described in the paper context.
- Open gap: The best upper bound remains a factor of 9 + ε, leaving a substantial gap in the approximation landscape.The paper explicitly identifies closing this gap as a direction for further work.
- Open directions: The reduction produces high-dimensional instances with d = Ω(n), although Johnson–Lindenstrauss projection reduces the dimension to O(log n/ε^2) while approximately preserving costs.The stated cost-preservation factor is (1+ε)^2.
- Open directions: Constant-dimensional inapproximability for k-means and hardness results for Euclidean k-median remain open questions.The paper also notes that its spectral graph-product analysis may have applications beyond this work.
A Appendix
The appendix proves an alternate triangle-free graph transformation by analyzing independent sets in a graph product. A maximal independent-set argument and expansion properties bound the product’s independent-set size.
- Alternate construction: The appendix constructs a triangle-free graph Ĝ in polynomial time with rel-IS(Ĝ) = rel-IS(G).The construction applies to an arbitrary graph G with maximum degree Δ.
- Expansion argument: The expansion argument relies on an (n,d,λ) graph with λ < d/4 and lower bounds on neighborhoods of vertex sets.These neighborhood bounds are derived from spectral and expander-mixing properties.
- Lower bound: The graph product G ⊗ H preserves an independent set from G by taking its product with all vertices of H.This gives the lower bound rel-IS(G ⊗ H) ≥ rel-IS(G).
- Upper bound: For the reverse direction, the proof groups vertices around a maximal independent set of G into stars and bounds the associated sets in H.Every vertex outside the maximal independent set has a neighbor in it, producing the star decomposition.