Close Menu

Dimensionality Reduction for \(k\)-Means and \(k\)-Medians Clustering


Nov 19, 2019 - 11:25am to 12:30pm


RE 119


Konstantin Makarychev, Associate Professor, Department of Computer Science, Northwestern University


We investigate dimensionality reduction for Euclidean \(k\)-means and \(k\)-medians clustering. We show that the cost of the optimal solution for \(k\)-means and \(k\)-medians is preserved up to a factor of  \( (1+\varepsilon) \) under a projection onto a random  \( \log k\)dimensional subspace. Further, the cost of every clustering is preserved within  \( (1+\varepsilon) \) 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\). Joint work with Yury Makarychev and Ilya Razenshteyn.

Event Type: 

Department of Applied Mathematics - Mathematical Finance and Stochastic Analysis Seminar