The bane of low-dimensionality clustering
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
The bane of low-dimensionality clustering. / Cohen-Addad, Vincent; De Mesmay, Arnaud; Rotenberg, Eva; Roytman, Alan.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . . ed. / A. Czumaj. Society for Industrial and Applied Mathematics, 2018. p. 441-456.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - The bane of low-dimensionality clustering
AU - Cohen-Addad, Vincent
AU - De Mesmay, Arnaud
AU - Rotenberg, Eva
AU - Roytman, Alan
PY - 2018
Y1 - 2018
N2 - In this paper, we give a conditional lower bound of n(k) on running time for the classic k-median and k-means clustering objectives (where n is the size of the input), even in low-dimensional Euclidean space of dimension four, assuming the Exponential Time Hypothesis (ETH). We also consider k-median (and k-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 nO(k11=d) or 2n11=d in d dimensions, our work shows that widely-used clustering objectives have a lower bound of n(k), even in dimension four. We complete the picture by considering the twodimensional case: we show that there is no algorithm that solves the penalized version in time less than no( p k), and provide a matching upper bound of nO( p k). 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.
AB - In this paper, we give a conditional lower bound of n(k) on running time for the classic k-median and k-means clustering objectives (where n is the size of the input), even in low-dimensional Euclidean space of dimension four, assuming the Exponential Time Hypothesis (ETH). We also consider k-median (and k-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 nO(k11=d) or 2n11=d in d dimensions, our work shows that widely-used clustering objectives have a lower bound of n(k), even in dimension four. We complete the picture by considering the twodimensional case: we show that there is no algorithm that solves the penalized version in time less than no( p k), and provide a matching upper bound of nO( p k). 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.
UR - http://www.scopus.com/inward/record.url?scp=85045560148&partnerID=8YFLogxK
U2 - 10.1137/1.9781611975031.30
DO - 10.1137/1.9781611975031.30
M3 - Article in proceedings
AN - SCOPUS:85045560148
SP - 441
EP - 456
BT - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms .
A2 - Czumaj, A.
PB - Society for Industrial and Applied Mathematics
T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Y2 - 7 January 2018 through 10 January 2018
ER -
ID: 203943325