Source-linked AI summary
Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics
Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
TL;DR
The paper addresses gaps in approximation schemes for facility location and clustering in graph metrics and for k-means in bounded-dimensional Euclidean space. It analyzes local search using weak r-divisions and establishes PTAS results across these settings, with graph results extending to minor-closed families.
Problem
A PTAS for k-means in low-dimensional Euclidean space with arbitrary k remained open, while planar facility location lacked a scheme for arbitrary weights.
Source: §1 · p. 2Method
The paper analyzes local search using weak r-divisions, which are used in the analysis rather than in the algorithm.
Source: §2.1 · p. 5Results
The paper establishes PTASs for planar facility location and graph k-median and k-means, and for bounded-dimensional Euclidean k-means.
Source: §1 · p. 2, §1.1 · pp. 3–4Takeaways & Limitations
The graph guarantees extend from planar graphs to graphs in any nontrivial minor-closed family.
Source: §1 · p. 2, §1.1 · p. 4The graph analysis requires r-divisions in minors of the input, a condition that does not hold for graphs of polynomial expansion.
Source: §2.1 · p. 5
Abstract
from arXiv · showhide
We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs; (2) $k$-median and $k$-means in edge-weighted planar graphs; (3) $k$-means in Euclidean spaces of bounded dimension. Our first and second results extend to minor-closed families of graphs. All our results extend to cost functions that are the $p$-th power of the shortest-path distance. The algorithm is local search where the local neighborhood of a solution $S$ consists of all solutions obtained from $S$ by removing and adding $1/\epsilon^{O(1)}$ centers.
1 Introduction
The paper gives polynomial-time approximation schemes for clustering and facility-location problems across several graph and Euclidean settings. Its results extend earlier bounds for k-means and address the long-standing difficulty of obtaining a planar facility-location scheme for arbitrary weights.
1.1 Results
- For every fixed dimension, the results include a PTAS for Euclidean k-means with arbitrary k, resolving an open question.Source: §1 · p. 2, §1.1 · p. 3
- It also gives PTASs for k-means in planar graphs and for k-median and k-means across nontrivial minor-closed graph families.Source: §1 · p. 2, §1.1 · p. 4
1.2 Related work
- Earlier work left planar facility location without a scheme for arbitrary weights, while local search for k-means had a 9+ε guarantee even in fixed dimension.Source: §1 · p. 2, §1.2 · p. 5
1.1 Results
- The paper gives the first PTAS for uniform facility location and k-median on planar graphs and, more generally, graphs in any fixed nontrivial minor-closed family.Source: §1 · p. 2
- The approach analyzes local search with bounded-size swaps, and the objective can use powered distances, including p=1 for k-median and p=2 for k-means.Source: §1.1 · pp. 3–4
- For p=1, a neighborhood of size c/ε² suffices for a 1+ε approximation in the graph facility-location result.Source: §1.1 · p. 4
2 Techniques
The analysis combines weak r-divisions with an isolation argument for comparing local and global clustering solutions, then identifies graph settings where bounded-neighborhood local search can remain far from optimal.
2.1 r-divisions in minors
- The analysis uses weak r-divisions and requires an input graph's minor to admit one, a property not shared by polynomial-expansion graphs.The decomposition is used only in the analysis, not by the algorithm.Source: §2.1 · p. 5
2.2 Isolation
- 1-1-isolated facilities serve nearly the same clients across local and global solutions; among the remaining global facilities, a substantial set can be removed at low cost.The removal guarantee does not require the local solution to be locally optimal or the global solution to be optimal.Source: §2.2 · p. 6
2.3 Tightness of the results
- For every w and t, excluding K_w as a t-shallow minor does not prevent 1/ε-neighborhood local search from returning cost at least 3OPT.The figure illustrates a size-3 local optimum costing at least 3OPT.Source: §2.3 · p. 6, Figure 1 · p. 7
- Low-density graph families also admit instances where local search with neighborhoods of size 1/ε returns cost at least 3OPT.The construction encodes the graph in Figure 1 as a low-density graph.Source: §2.3 · p. 7
3 Preliminaries
The preliminaries set up graph and Euclidean r-divisions, Voronoi-based contractions, and separation properties used in the local-search analysis.
3 Preliminaries
- A preliminary distance inequality bounds a p-th-power distance by twice the sum of the two corresponding p-th-power distances through an intermediate point.The proof invokes the triangle inequality and binomial theorem.Source: §3 · pp. 7–8
3.1 Graph r-division and other definitions
- A weak r-division partitions graph edges into regions of at most r vertices, with O(|V(G)|/r) regions and total boundary size O(|V(G)|/r^1/2).Such divisions exist for every graph in a nontrivial minor-closed family.Source: §3.1 · p. 8
- Contracting each connected Voronoi cell around a center produces a graph that remains in the same minor-closed family.The Voronoi partition assigns each vertex to its nearest center, breaking ties by a fixed priority order.Source: §3.1 · pp. 8–9
3.2 Euclidean space r-division
- In fixed-dimensional Euclidean space, a weak r-division has O(|C|/r) regions of at most r points and total boundary size O(|C|/r^1/d).Each region's boundary separates its interior points from points outside the region in the Voronoi diagram.Source: §3.2 · p. 9
3.3 Properties of the r-Divisions
- Across graph and Euclidean r-divisions, a point in one region can be served by a boundary center in that region no farther away than a point in another region.The graph and Euclidean versions are stated in Lemmas 3.8 and 3.9.Source: §3.3 · pp. 9–10
4 Facility Location in minor-closed graphs: Proof of Theorem 1.3
The proof partitions the contracted graph into regions and compares the local solution with mixed solutions that replace facilities region by region.
4 Facility Location in minor-closed graphs: Proof of Theorem 1.3
- The proof assigns local and optimal facilities to regions of an r-division of the Voronoi-contracted graph, then forms each mixed solution by swapping facilities within one region.The division uses r=1/ε^2; regional sets include vertices mapping to region boundaries.Source: §4 · p. 10
- Each regional mixed solution differs from the local solution by at most 1/ε^2 facility changes, so it lies within the allowed local-search neighborhood.The bound follows because each region contains at most r=1/ε^2 vertices after contraction.Source: §4 · p. 10
- A boundary facility can serve a client at no greater distance than a facility outside its region, which bounds the change in client service cost under a regional swap.The argument applies the separation property of the r-division to compare local, global, and mixed assignments.Source: §4 · pp. 10–11
- Summing the regional boundary counts gives an O(ε) contribution relative to the combined local and global facility sets.The bound uses the r-division boundary-size property with r=1/ε^2.Source: §4 · p. 11
- The proof combines local optimality with the regional cost comparison and boundary bounds to complete Theorem 1.3.The stopping condition supplies the local-optimality inequality used in the final summation.Source: §4 · pp. 11–12
5 Clusters in minor-closed graphs: Proof of Theorem 1.2
The proof uses isolation, r-divisions, and regional swaps to compare a local clustering solution with a modified optimal solution in minor-closed graphs.
5 Clusters in minor-closed graphs: Proof of Theorem 1.2
- The proof constructs G1 by removing facilities while controlling its cost, then adds r-division boundary facilities to form G*.The construction also distinguishes good clients from bad clients according to whether their assignments fall in isolated-region differences.Source: §5 · pp. 12–13
- For region R, MR = (L − L(R)) ∪ G*(R); Lemma 5.4 gives |MR − L| + |L − MR| = O(1/ε^12) and |MR| ≤ k.C is the union of O(1/ε^5) parts of S.Source: §5 · p. 13
- For bad clients, the cost comparison includes reassignment costs for isolated facilities; summing these terms uses the small fraction of clients crossing isolated-region assignments.The proof partitions clients into Λ1, Λ2, and Λ3 and applies the isolated-region reassignment bounds.Source: §5 · pp. 14–16
- For good clients, a regional swap increases cost by at most the global-versus-local cost difference when the global facility is in that super-region, and otherwise by zero.The result uses the separation property of the r-division.Source: §5 · p. 15
- Local optimality for every mixed solution, combined with the client-cost bounds and the cost guarantee for G1, completes the proof of Theorem 1.2.The argument applies when ε is sufficiently small relative to p and ε1.Source: §5 · pp. 16–17
6 Clusters in Euclidean space : Proof of Theorem 1.1
The Euclidean proof adapts the minor-closed-graph argument by constructing r-divisions of facility point sets and then continuing with the earlier proof.
6 Clusters in Euclidean space : Proof of Theorem 1.1
- For fixed dimension d, the proof forms r-divisions with r=1/ε^7d for isolated facility sets and the remaining facilities, then adds their boundary points to G1.It defines good clients outside isolated-region assignment differences and proceeds from Lemma 5.1 of the graph proof.Source: §6 · pp. 17–18
7 Reducing the number of clusters : Proof of Theorem 2.2
Theorem 2.2 bounds the cost of removing a substantial set of facilities that are not in 1-1 isolated regions. Its proof uses bounded-cost reassignment, then selects facilities whose reassignment targets remain outside the removed set.
Theorem 2.2
- Removing at least ε^3\bar{k}/6 facilities yields cost at most (1 + 2^(3p+1)ε)cost(G) + 2^(3p+1)εcost(L), where \bar{k} counts G facilities not in 1-1 isolated regions.The theorem applies to two solutions L and G for k-clustering with exponent p; L need not be locally optimal or G globally optimal.Source: §7 · p. 18
Lemma 7.1
- Reassigning clients of all non-isolated facilities through a map φ increases cost by at most 2^(3p+1)ε^-2(cost(L) + cost(G)).The proof constructs a fractional reassignment and bounds its total cost increase.Source: §7 · pp. 18–20
Proof of Theorem 2.2
- A directed graph of reassignment targets has outdegree at most one, so three colors can separate every arc’s endpoints.The largest color class contains at least one third of the non-isolated facilities; partitioning it and averaging selects a removable subset with low reassignment cost.Source: §7 · p. 18
- At least half of the facilities counted by \bar{k} are non-isolated facilities of G, giving |\tilde{G}| ≥ \bar{k}/2.The counting argument uses that each non-1-1-isolated region contains at least two facilities of L.Source: §7 · p. 18
8 Postponed proofs
The proof constructs weak r-divisions recursively by splitting a point set with a sphere separator. A concavity argument supplies the positive slack needed to bound the total boundary contribution.
8.1 Proof of existence of weak r-divisions in Euclidean space
- When |C| > r, the recursive construction uses a sphere separator, then recurses on the points inside and outside the separator together with its boundary set.The returned division combines the separator set with the two recursively constructed sets.Source: §8.1 · p. 20
- The proof reduces Property 4 to bounding the total number of region-boundary incidences with the separator set.It defines b(n) as that total for a set C of size at most n.Source: §8.1 · p. 20
- Strict concavity gives f(σ) = f(1 − σ) = 1 + δ for δ > 0, providing slack for the inductive bound on b(n).The proof chooses γ using this positive δ to establish the induction step.Source: §8.1 · pp. 20–21