The Bane of Low-Dimensionality Clustering

Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg +1

In this paper, we give a conditional lower bound of $n^{\Omega (k)}$ on running time for the classic k-median and k-means clustering objectives (where n is the size of the input), even i…