View article

We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs; (2) -median and -means in edge-weighted planar graphs; and (3) -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 th power of the shortest-path distance. The algorithm is local search, where the local neighborhood of a solution consists of all solutions obtained from by removing and adding centers.