TCS+ Talk
Annenberg 308
Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics
Claire Mathieu,
ENS,
Available remotely at Google Hangouts:
Abstract: 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 spaces 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 p-th 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/ϵO(1) centers. Joint work with Vincent Cohen-Addad and Philip N. Klein.
For more information, please contact Thomas Vidick by email at [email protected].
Event Series
TCS+ Talks