Towards optimal lower bounds for k-median and k-means coresets.

Vincent Cohen-Addad Kasper Green Larsen David Saulpic Chris Schwiegelshohn

Published in: STOC (2022)

Keyphrases

lower bound
k means
worst case
optimal solution
dynamic programming
optimal cost
upper bound
objective function
cluster analysis
lower and upper bounds
quadratic assignment problem
clustering algorithm
np hard
similarity measure
data clustering
branch and bound algorithm
learning theory
minimum cost