Dec 4 2019

Computer Science Theory Seminar: Dimensionality reduction for k-means and k-medians clustering, by Yury Makarychev

December 4, 2019

4:15 PM - 5:05 PM


1325 SEO


Chicago, IL

Yury Makarychev (TTI Chicago): Dimensionality reduction for k-means and k-medians clustering

Consider an instance of Euclidean k-means or k-medians clustering. We show that the cost of the optimal solution is preserved up to a factor of (1+?) under a projection onto a random O(log(k/?)/?^2)-dimensional subspace. Further, the cost of every clustering is preserved within (1+?). More generally, our result applies to any dimensionality reduction satisfying a mild sub-Gaussian-tail condition. Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean k-clustering with the distances raised to the p-th power for any constant p.

Based on a joint work with Konstantin Makarychev and Ilya Razenshteyn.

Please click here to make changes to, or delete, this seminar announcement.


Will Perkins

Date posted

Dec 13, 2019

Date updated

Dec 13, 2019


Yury Makarychev | (TTI Chicago)