
CMUCS02193
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS02193
Adventures in UltraSmallSpace Clustering
Adam Meyerson, Liadan O'Callaghan*, Serge Plotkin*
December 2002
CMUCS02193.ps
CMUCS02193.pdf
Keywords: Algorithms, approximation, clustering, sampling,
kmedian, facility location
We give a samplingbased algorithm for the kMedian problem,
with running time where [.....] k is the desired cluster number and
is a confidence parameter. This is the first kMedian algorithm
with fully polynominial running time that is independent of n,
the size of the data set. It gives a solution that is, with high
probability, an O(1) approximation if each cluster in the optimal
solution has [....] points. We give nearmatching lower bounds showing that
this assumption about cluster size is necessary. We also present a
related algorithm for finding a clustering that excludes a small number
of outliers.
13 pages
* Department of Computer Science, Stanford University
