Clustering under Local Stability: Bridging the Gap between Worst-Case and Beyond Worst-Case Analysis.

Maria-Florina Balcan Colin White

Published in: CoRR (2017)

Keyphrases

worst case analysis
worst case
average case
clustering algorithm
greedy algorithm
upper bound
lower bound
greedy heuristic
np hardness
k means
np hard
approximation algorithms
sample size
data points
theoretical analysis
convergence rate
uniform distribution
computational complexity
learning algorithm