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

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$-mea…