Local search yields approximation schemes for k-means and k-median in\n Euclidean and minor-free metrics

Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu

This paper, titled "Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics," is a landmark result in theoretical computer science. It provides a surprisingly simple answer to a long-standing question: Can a basic local search algorithm find near-optimal clusters in complex geometric and topological spaces?

TL;DR

The authors prove that a simple local search algorithm—swapping a small, constant number of centers—provides the first Polynomial-Time Approximation Schemes (PTASs) for $k$-means and $k$-median clustering in planar graphs and minor-free metrics. It also resolves a major open question by providing a PTAS for $k$-means in Euclidean space for an arbitrary number of clusters $k$.

What Problem Does This Paper Address?

Clustering is the bread and butter of data science, but from a mathematical perspective, it is notoriously difficult. Problems like $k$-means (minimizing the sum of squared distances) and $k$-median (minimizing the sum of distances) are NP-hard.

In general metric spaces, we can only hope for "constant-factor" approximations (e.g., an algorithm that is guaranteed to be no worse than 9 times the optimal cost). However, for specific types of data—like points on a map (planar graphs) or points in low-dimensional space (Euclidean space)—we want a PTAS: an algorithm that can get within a factor of $(1 + \epsilon)$ of the optimum for any $\epsilon > 0$.

Before this paper, PTASs existed for these problems only under restrictive conditions (like when the number of clusters $k$ is fixed and small). The big challenge was finding a PTAS that works even when $k$ is very large (part of the input), particularly for $k$-means in the plane.

Methods

The beauty of this paper lies in the simplicity of the algorithm it analyzes: Local Search.

  1. The Algorithm: Start with any $k$ centers. Look at the "neighborhood" of your current solution. If you can swap out a small number of centers ($s = 1/\epsilon^{O(1)}$) for new ones and reduce the total cost by a certain margin, do it. Repeat until no such swap improves the cost.
  2. The Analysis: The real heavy lifting is in the proof. To show that a local optimum is close to the global optimum, the authors use:
  3. $r$-divisions: A technique to decompose a graph or Euclidean space into small regions with very few "boundary" points. This allows the authors to analyze the cost locally.
  4. Isolation Technique: This is the "secret sauce." Comparing a local solution to a global one is hard because of the strict constraint that you must have exactly $k$ centers. The authors developed a way to identify "isolated" regions where local and global centers serve almost the same clients, allowing them to "prune" the global solution for comparison without losing too much accuracy.

Datasets

As a theoretical paper, no empirical datasets were used. The results are mathematical proofs that hold true for any input that fits the specified categories:

  • Edge-weighted planar graphs.
  • Minor-closed families of graphs (a broad category including planar graphs and graphs embeddable on surfaces like a torus).
  • $d$-dimensional Euclidean space.

Key Insights and Ideas

  • Local Search is "Smarter" Than We Thought: It was already known that local search gives a constant-factor approximation. This paper shows that if you just increase the "swap size" to a larger (but still constant) number, the algorithm naturally converges to a near-optimal solution in structured spaces.
  • Structure Matters: The proof relies on the fact that planar graphs and Euclidean spaces have "small separators." You can cut the space into pieces without hitting too many points. Local search exploits this structure by effectively optimizing within these pieces.
  • The Power of $p$: The results aren't just for $k$-means ($p=2$) or $k$-median ($p=1$). They extend to any cost function based on the $p$-th power of the distance, making the framework very robust.

Key Results

  • First PTAS for Planar/Minor-Free Graphs: The authors provide the first $(1+\epsilon)$-approximation for $k$-means, $k$-median, and uniform facility location in these graph types.
  • Solving the Euclidean $k$-means Mystery: They provide the first PTAS for $k$-means in $d$-dimensional Euclidean space for arbitrary $k$. Previously, the best-known bound for arbitrary $k$ was a 9-approximation.
  • Complexity: The algorithm runs in $n^{O(s)}$ time, where $s$ depends on $1/\epsilon$. While the exponent can be large, it is strictly polynomial for a fixed $\epsilon$.

Limitations and Future Work

  • Practicality of the Exponent: While "polynomial," the neighborhood size $1/\epsilon^{O(1)}$ means that for a very small $\epsilon$ (like 0.01), the algorithm would be far too slow for real-world big data. Future work could focus on making these PTASs "efficient" (EPAS), where the exponent of $n$ does not depend on $1/\epsilon$.
  • Non-Uniform Costs: The facility location result is for "uniform" costs (every facility costs the same to open). Extending this to non-uniform costs in minor-free graphs remains an area for exploration.
  • Doubling Metrics: The authors note that while they focused on Euclidean and minor-free spaces, concurrent work by others has explored similar results for "doubling metrics," suggesting a broader trend toward understanding local search in structured metric spaces.

Summary updated

Abstract

We give the first polynomial-time approximation schemes (PTASs) for the\nfollowing problems: (1) uniform facility location in edge-weighted planar\ngraphs; (2) $k$-median and $k$-means in edge-weighted planar graphs; (3)\n$k$-means in Euclidean spaces of bounded dimension. Our first and second\nresults extend to minor-closed families of graphs. All our results extend to\ncost functions that are the $p$-th power of the shortest-path distance. The\nalgorithm is local search where the local neighborhood of a solution $S$\nconsists of all solutions obtained from $S$ by removing and adding\n$1/\\epsilon^{O(1)}$ centers.\n
BibTeX
@article{cohenaddad2016local,
  author = {Vincent Cohen-Addad and Philip N. Klein and Claire Mathieu},
  title = {{Local search yields approximation schemes for k-means and k-median in\textbackslash\{\}n Euclidean and minor-free metrics}},
  journal = {SIAM Journal on Computing},
  year = {2016},
}
Figure