LOCAL SEARCH YIELDS APPROXIMATION SCHEMES FOR k-MEANS AND k-MEDIAN IN EUCLIDEAN AND MINOR-FREE METRICS

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; and (3) k-means in Euclidean space 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 pth 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(Theta(1)) centers.