The bane of low-dimensionality clustering

Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, Alan Roytman

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

194 Downloads (Pure)


In this paper, we give a conditional lower bound of <i>n</i><sup>ω(<i>k</i>)</sup> on running time for the classic <i>k</i>-median and <i>k</i>-means clustering objectives (where <i>n</i> is the size of the input), even in low-dimensional Euclidean space of dimension four, assuming the Exponential Time Hypothesis (ETH). We also consider <i>k</i>-median (and <i>k</i>-means) with penalties where each point need not be assigned to a center, in which case it must pay a penalty, and extend our lower bound to at least three-dimensional Euclidean space. This stands in stark contrast to many other geometric problems such as the traveling salesman problem, or computing an independent set of unit spheres. While these problems benefit from the so-called (limited) blessing of dimensionality, as they can be solved in time <i>n</i><sup><i>O</i></sup>(<i>k</i><sup>1--1/<i>d</i>)</sup> or 2<sup><i>n</i></sup><sup>1--1/<i>d</i></sup> in <i>d</i> dimensions, our work shows that widely-used clustering objectives have a lower bound of <i>n</i><sup>ω(<i>k</i>)</sup>, even in dimension four. We complete the picture by considering the two-dimensional case: we show that there is no algorithm that solves the penalized version in time less than [Equation], and provide a matching upper bound of [Equation]. The main tool we use to establish these lower bounds is the placement of points on the moment curve, which takes its inspiration from constructions of point sets yielding Delaunay complexes of high complexity.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherSociety for Industrial and Applied Mathematics
Publication date2018
ISBN (Electronic)978-1-61197-503-1
Publication statusPublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms - Astor Crowne Plaze, New Orleans French Quarter , New Orleans , United States
Duration: 7 Jan 201810 Jan 2018
Conference number: 29


Conference29th Annual ACM-SIAM Symposium on Discrete Algorithms
LocationAstor Crowne Plaze, New Orleans French Quarter
Country/TerritoryUnited States
CityNew Orleans
SeriesProceedings of the Twenty-ninth Annual Acm-siam Symposium


Dive into the research topics of 'The bane of low-dimensionality clustering'. Together they form a unique fingerprint.

Cite this