Journal
SIAM JOURNAL ON COMPUTING
Volume 48, Issue 2, Pages 644-667Publisher
SIAM PUBLICATIONS
DOI: 10.1137/17M112717X
Keywords
approximation schemes; k-means; k-median; facility location; Euclidean metric; planar graph; minor-free graphs
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available