Source-linked AI summary
Local Search Yields a PTAS for k-Means in Doubling Metrics
Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour
TL;DR
Finding an efficient k-means algorithm with a proven cost bound has been a longstanding challenge. The paper uses local search and proves a (1 + ϵ)-approximation for k-means in doubling metrics, with related PTAS results for other clustering and facility-location problems.
Problem
Finding an efficient k-means algorithm with a proven theoretical bound on the returned solution’s cost is a longstanding challenge in clustering.
Source: §1 · p. 3Method
Local search repeatedly replaces up to ρ centres with a cheaper set of centres until no such improvement remains.
Source: §1.1 · p. 4Results
A (1 + ϵ)-approximation for k-means in metrics with doubling dimension d.
Source: §1.1 · p. 5Takeaways & Limitations
The approach also gives PTAS results for uncapacitated facility location and generalized k-median in doubling metrics, and a true PTAS for k-median in the Euclidean plane.
Source: §7 · p. 27Whether fixed-dimensional k-means admits an EPTAS, including a near-linear-time EPTAS in the Euclidean plane, remains open.
Source: §7 · p. 27
Abstract
from arXiv · showhide
The most well known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly $k$-means: given a set of data points and a parameter $k$, select $k$ centres and partition the data points into $k$ clusters around these centres so that the sum of squares of distances of the points to their cluster centre is minimized. Typically these data points lie $\mathbb{R}^d$ for some $d\geq 2$. $k$-means and the first algorithms for it were introduced in the 1950's. Since then, hundreds of papers have studied this problem and many algorithms have been proposed for it. The most commonly used algorithm is known as Lloyd-Forgy, which is also referred to as "the" $k$-means algorithm, and various extensions of it often work very well in practice. However, they may produce solutions whose cost is arbitrarily large compared to the optimum solution. Kanungo et al. [2004] analyzed a simple local search heuristic to get a polynomial-time algorithm with approximation ratio $9+\epsilon$ for any fixed $\epsilon>0$ for $k$-means in Euclidean space. Finding an algorithm with a better approximation guarantee has remained one of the biggest open questions in this area, in particular whether one can get a true PTAS for fixed dimension Euclidean space. We settle this problem by showing that a simple local search algorithm provides a PTAS for $k$-means in $\mathbb{R}^d$ for any fixed $d$. More precisely, for any error parameter $\epsilon>0$, the local search algorithm that considers swaps of up to $\rho=d^{O(d)}\cdot{\epsilon}^{-O(d/\epsilon)}$ centres at a time finds a solution using exactly $k$ centres whose cost is at most a $(1+\epsilon)$-factor greater than the optimum. Finally, we provide the first demonstration that local search yields a PTAS for the uncapacitated facility location problem and $k$-median with non-uniform opening costs in doubling metrics.
1 Introduction
The paper closes the fixed-dimensional k-means PTAS gap with a local-search algorithm, then extends its guarantees to doubling metrics and related clustering objectives. Its proof partitions local- and global-optimum centres into small swap sets, with a randomized partition that limits reassignment costs.
1.1 Our result and technique
- The result resolves the fixed-dimensional Euclidean k-means PTAS question, where local search had previously achieved a 9 + ϵ approximation.The introduction identifies a PTAS for fixed-dimensional k-means as an open problem; the 9 + ϵ guarantee is attributed to Kanungo et al..Source: §1 · p. 3, §1.1 · p. 4
- Local search starts from k candidate centres and repeatedly replaces up to ρ centres with a cheaper set until no improving swap remains.Each iteration takes |C|^O(ρ) time, polynomial when ρ is constant; a standard modification ensures polynomially many iterations.Source: §1.1 · p. 4
- A ρ-swap local-search algorithm is a (1 + ϵ)-approximation for k-means in metrics with doubling dimension d.The introduction specifies ρ = d^O(d) · ϵ^-O(d/ϵ) for the Euclidean result; the doubling-metric theorem uses a stated ρ(ϵ, d).Source: §1.1 · pp. 4–5
- For any fixed q ≥1, the analysis extends to minimizing the sum of q’th powers of distances in doubling metrics.The q = 2 case is k-means and q = 1 is k-median.Source: §1.1 · p. 5
- The Euclidean k-means result also gives a sub-exponential-time (1+ϵ)-approximation for d = σ log n / log log n, for sufficiently small absolute σ.For d = O(log log n / log log log n), the paper states a quasi-polynomial-time approximation scheme.Source: §1.1 · p. 5
- Theorem 2 gives a (1+ϵ)-approximation for uncapacitated facility location in doubling metrics using local search that adds and/or drops up to ρ centres.The analysis carries over because the swaps partition local- and global-optimum centres, and facility location does not require the exactly-k partitioning step.Source: §1.1 · p. 6
- Theorem 3 gives a (1 + ϵ)-approximation for generalized k-median in metrics with doubling dimension d, subject to the resulting solution having at most k facilities.The problem permits centre opening costs and at most k chosen centres; the prior best approximation cited was 5 in general metrics.Source: §1.1 · p. 6
1.2 Proof Outline
- The proof uses a randomized partition of the local- and global-optimum centres into small parts, yielding an overall cost ratio of 1 + O(ϵ).A net around each filtered local centre captures nearby global centres; when a net is cut, reassignment costs are bounded and the event occurs with small probability.Source: §1.2 · p. 7
2 Notation and Preliminaries
The section formulates k-means over candidate centres in a metric space, with the objective defined by squared distance to the nearest selected centre. It also sets out the local-search swap condition and notation used to analyze its solutions.
2 Notation and Preliminaries
- A candidate-centre set C reduces Euclidean k-means to the discrete case with at most a (1 + ϵ) loss; it can be computed in O(nϵ^-d log(1/ϵ)) time.The supplied passage gives |C| = O(nϵ^-d log(1/ϵ)).Source: §2 · p. 7
- For any improving swap, the local-search heuristic replaces at most ρ selected centres with the same number of centres from C.The algorithm begins with k centres and continues while a cheaper such swap exists.Source: §2 · p. 8
- In the discrete formulation, choose k centres from C to minimize the sum of squared distances from each point to its nearest centre.Assigning each point to its nearest selected centre realizes the objective.Source: §2 · p. 8
- A standard modified improvement threshold gives polynomial termination, and the local-search analysis bounds the returned cost using the approximation guarantee for locally optimal solutions.The passage states cost(S) ≤ α/(1−ϵ) cost(O) when no possible swap meets the improvement threshold.Source: §2 · p. 8
- The analysis assumes disjoint current and optimal centre sets without loss of generality and takes ϵ sufficiently small for its bounds.The passage permits duplicating locations to make the sets disjoint.Source: §2 · p. 8
3 Local Search Analysis for Rd
This section analyzes local search for k-means in fixed-dimensional Euclidean space, showing how partitioned test swaps yield a near-optimality bound for a ρ(ϵ, d)-swap local optimum. It also bounds the probability of bad points and uses coresets to reduce the work per iteration.
3 Local Search Analysis for Rd
- 1 + O(ϵ): every ρ(ϵ, d)-swap local optimum in Rd has cost at most this factor times the optimum.The section defines ρ(ϵ, d) = 32 · (2d)8d · ϵ−36·d/ϵ.Source: §3 · pp. 8–9
- For each part P, local optimality gives a nonnegative swap-cost change; test swaps are chosen to limit reassignment costs for points whose centers are separated.The proof partitions O ∪ S into parts with equal numbers of centers from O and S, each no larger than ρ(ϵ, d).Source: §3 · p. 9
- Filtering gives each center i a proxy η(i) within ϵ · D_i, while distinct centers are separated by at least ϵ · max{D_i, D_i′}.The filtering and partitioning schemes are proof tools; the k-means algorithm itself is the local search described earlier.Source: §3 · p. 9
3.1 Every Centre is Close to Some Pair in T
- 5 · D_i′ bounds δ(i′, A) for every center i′ when A contains at least one center from each pair in T.The proof uses a walk whose step lengths decrease geometrically every other step.Source: §3.1 · p. 11
3.2 Good Partitioning of O ∪S and Proof of Theorem 4
- Each randomized partition has balanced parts of size at most ρ(ϵ, d), retains a center from every pair in T after each swap, and separates each pair in N with probability at most ϵ.The analysis of local search after establishing this partitioning scheme does not use the geometry of the metric; the proof of the scheme does use properties of Rd.Source: §3.2 · p. 13
- 71 · (c*_j + c_j) bounds the reassignment cost for a bad point when its assigned center is closed.The analysis states that a bad point occurs with probability at most ϵ over the random partition, compensating for this weaker bound.Source: §3.2 · p. 15
- For good points, the two cases reassign a point when its current centre closes, using the optimum centre and a nearby proxy to bound the added travel.When Dσ∗(j) < ϵ · Dσ(j), the proxy-distance filtering gives an intermediate bound of at most ϵ(1 + ϵ)Dσ(j).Source: §3.2 · p. 16
- Averaging over the random partition π, each point is bad with probability at most ϵ, by Theorem 5 and the definition of bad.Source: §3.2 · p. 17
3.3 Running Time Analysis
- The local-search algorithm extends to weighted point sets, with each point’s contribution to clustering cost multiplied by its weight.Source: §3.3 · p. 18
- O((k/ϵ)^ζ) time per iteration is obtained using a (k, ϵ)-coreset of size O(k^3/ϵ^(d+1)) and a centroid set of size O(log(1/ϵ)k^3/ϵ^(2d+1)), where ζ = d^O(d) · ϵ^-O(d/ϵ).The analysis also gives a crude per-step bound of O((nϵ^-d log(1/ϵ))^ρ) and states that the number of local-search steps is polynomial in the input bit complexity.Source: §3.3 · p. 18
4 The Partitioning Scheme: Proof of Theorem 5
The partitioning scheme uses randomized bands and cells to keep related centres together while limiting the size of each part. Cleanup steps preserve the desired pairings and balance the number of local and optimal centres in every part.
4 The Partitioning Scheme: Proof of Theorem 5
- The scheme groups centres by geometric distance buckets, then uses random offsets for bands and grid cells to make nearby pairs unlikely to be separated.Bands combine b consecutive buckets; cell width is roughly Θ(d/ε^(ℓb)) for band Bℓ.Source: §4 · p. 19, §4.1 · pp. 19–20
4.1 Partitioning {Ga : a ∈Z}
- The construction moves selected centres into the cell containing their φ-mapped partner so that each pair in T remains together.Centres with zero D are handled separately, since no pair in T or N has exactly one endpoint in G−∞.Source: §4 · p. 19, §4.1 · p. 20, §4.3 · p. 22
4.2 Properties of the Partitioning Scheme
- Each initial part has bounded size, and every pair in N is separated into different parts with probability at most ε.The size bound follows from packing; the separation bound accounts for cuts at the band, grid-cell, and cleanup stages.Source: §4.2 · pp. 20–21, §4.3 · p. 22
4.3 Balancing the Parts
- Balancing merges initial parts into parts with equal numbers of O and S centres while retaining bounded size and the pair-separation guarantee.The balancing lemma finds a nonempty union of at most 2Y^3 sets with zero imbalance when each set has size at most Y.Source: §4.3 · pp. 22–23
5 Proof of Theorem 1 and Extension to ℓq q-norm k-clustering
The Euclidean analysis is adapted to doubling metrics using hierarchical decompositions, then extended to fixed-q clustering objectives. The resulting local-search guarantees include a PTAS for k-means in doubling metrics and a (1 + O(ε))-approximation for fixed q.
5 Proof of Theorem 1 and Extension to ℓq q-norm k-clustering
- For doubling metric spaces of dimension d, the analysis establishes a PTAS using ρ-swap local search, with ρ = ρ(ϵ, d) = 32 · d16d · ϵ−256d/ϵ.The rest of the proof remains unchanged, except for the Euclidean-specific parts identified in the proof of Theorem 5 and Lemma 7.Source: §5 · p. 23, §5.1 · p. 23
5.1 Extending to Doubling Metrics
- The doubling-metric construction uses hierarchical clusters to bound cell size and retain the pair-separation probability needed by the partitioning argument.The proof bounds the probability that a pair in the same band falls into different clusters by ε/4, then applies the earlier partitioning analysis.Source: §5.1 · pp. 23–24
5.2 Extending to ℓq q-norm k-clustering
- For any fixed q ≥ 1, the ℓq objective for k-clustering admits a (1 + O(ε))-approximation via local search with swaps of size ρ = d^O(d) · (2q/ε)^−d·2q/ε.Source: §5.2 · p. 25
6 Extending to the uncapacitated facility location and generalized k-median problems
The section extends local-search approximation results to uncapacitated facility location and generalized k-median. For facility location, a polynomial-time variant achieves a PTAS guarantee; the analysis also extends to q-power objectives in doubling dimensions.
Uncapacitated facility location
- Every locally optimal facility-location solution has cost at most (1 + O(ϵ)) times optimum using at most 2 · |C| test swaps.Replacing the cost condition in the local-search algorithm gives a polynomial-time PTAS variant.Source: §6 · p. 25
- The facility-location analysis uses randomized partitions of the local and global solutions, with each neighboring pair separated with probability at most ϵ.The partition construction drops the balancing step because local and global solutions need not have equal size.Source: §6 · p. 25
Generalized k-median
- For generalized k-median, artificial zero-opening-cost facilities placed far from the data let the proof align local and global solutions before reusing the partitioning result.Generalized k-median combines a cardinality bound with facility opening costs.Source: §6 · p. 26
ℓq objectives
- The facility-location and generalized k-median results extend to objectives using the q’th power of distances in doubling dimensions.The extension uses arguments nearly identical to those for the ℓq extension of k-means.Source: §6 · p. 26
7 Conclusion
The conclusion presents PTAS results for k-means and related clustering and facility-location problems in doubling metrics. It also notes a dimension-dependent running time and leaves faster schemes as open possibilities.
Conclusion
- The paper gives PTAS results for k-means in constant-dimensional Euclidean and doubling metrics, and extends the results to ℓq objectives and facility location and generalized k-median in doubling metrics.It also reports a first approximation for k-median in doubling metrics and a local-search PTAS for k-median in the Euclidean plane.Source: §7 · p. 27
Running time
- A single local-search step takes O(kρ) time for k-means, with ρ = d^O(d)·ϵ^-O(d/ϵ); under ETH, the dependence on d cannot be improved much.The stated ETH implication rules out a single-iteration bound of O(k·exp(d^(1−δ))·f(ϵ)) for constant δ.Source: §7 · p. 27
Open questions
- An EPTAS for fixed dimension may still be possible, and the fastest PTAS for the Euclidean plane—especially one near-linear in n—remains an open question.Source: §7 · p. 27