TCS+ Talk

Wednesday October 26, 2016 10:00 AM

Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics

Speaker: Claire Mathieu, ENS
Location: Annenberg 308

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.


Series TCS+ Talks

Contact: Thomas Vidick