Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
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, (3) k-means in Euclidean space of bounded dimension. Our first and second results extend to minor-closed families of graphs. All our results …