Optimal Time Bounds for Approximate Clustering.
Clustering is a fundamental problem in unsupervised learning, and has been studied widely both as a problem of learning mixture models and as an optimization problem. In this paper, we study clustering with respect to the k-median objective function, a natural formulation of clustering in which we attempt to minimize the average distance to cluster centers. One of the main contributions of this paper is a simple but powerful sampling technique that we call successive sampling that could be of independent interest. We show that our sampling procedure can rapidly identify a small set of points (of size just O(k log \frac{n}{k})) that summarize the input points for the purpose of clustering. Using successive sampling, we develop an algorithm for the k-median problem that runs in O(nk) time for a wide range of values of k and is guaranteed, with high probability, to return a solution with cost at most a constant factor times optimal. We also establish a lower bound of (nk) on any randomized constant-factor approximation algorithm for the k-median problem that succeeds with even a negligible (say \frac{1}{100}) probability. The best previous upper bound for the problem was (nk), where the -notation hides polylogarithmic factors in n and k. The best previous lower bound of (nk) applied only to deterministic k-median algorithms. While we focus our presentation on the k-median objective, all our upper bounds are valid for the k-means objective as well. In this context our algorithm compares favorably to the widely used k-means heuristic, which requires O(nk) time for just one iteration and provides no useful approximation guarantees.
Introduction
Given a set of points and pairwise distances between the points, the goal of clustering problems
is to partition the points into a number of sets such that points in each set are "close" with respect
to some objective function. Clustering algorithms are widely used to organize large data sets in
areas such as data mining and information retrieval. For example, we may wish to partition a set
of web logs to infer certain usage patterns, or divide a corpus of documents into a small number
of related groups. Given a set of points and associated interpoint distances, let the median of
the set be the point in the set that minimizes the sum of distances to all other points in the set.
(Remark: The median is essentially the discrete analog of the centroid, and is also called the
medoid [9].) The clustering problem we consider asks us to partition n weighted points into k sets
such that the sum, over all sets, of the weight of a point times the distance to the median of its
set is minimized. Approaches to this type of clustering problem, such as the k-means heuristic,
have been well-studied [4, 9]. We refer to this problem as the clustering variant of the classic
k-median problem; the k-median problem asks us to mark k of the points such that the sum over
all points x of the weight of x times the distance from x to the nearest marked point is minimized.
It is straightforward to see that we can convert a solution to the k-median problem into a solution
for its clustering variant in O(nk) time; thus we focus on the k-median problem when developing
our upper bounds. We also restrict our attention to the metric version of the problems throughout
this paper; the given distance matrix defines a metric space over the set of input points, that is,
the distances are nonnegative, symmetric, satisfy the triangle inequality, and the distance between
points x and y is zero if and only if y. (Remark: For the sake of brevity we write "k-median
problem" to mean "metric k-median problem" throughout the remainder of the paper.)
Since problem instances in the application areas mentioned above tend to be large, we are motivated
to ask how input characteristics such as the point weights and interpoint distances affect
the complexity of the k-median problem and its clustering variant. Weighted points are useful in a
number of applications; for example, we may wish to prioritize the objects in the input. We ask the
following natural question: Does allowing inputs with arbitrary point weights incur a substantial
time penalty? We note that even for moderate weights, say O(n 2 ), the naive approach of viewing
a weighted point as a collection of unit-weight points increases the input size dramatically. For
certain applications, the interpoint distances may lie in a relatively small range. Thus we are motivated
to ask: Does constraining distances to a small range admit substantially faster algorithms?
We resolve both of the above questions for a wide range of input parameters by establishing a time
bound of (nk) for the k-median problem and its clustering variant. Thus, we show that in many
cases, having large point weights does not incur a substantial time penalty, and, that we cannot
hope to develop substantially faster algorithms even when the interpoint distances lie in a small
range.
Before stating our results we introduce some useful terminology that we use throughout this pa-
per. Let U denote the set of all points in a given instance of the k-median problem; we assume that
U is nonempty. A configuration is a nonempty subset of U . An m-configuration is a configuration
of size at most m. For any points x and y in U , let w(x) denote the nonnegative weight of x, and let
d(x; y) denote the distance between x and y. The cost of any configuration X , denoted cost (X), is
defined as
We denote the minimum cost of any m-configuration by OPT m .
For brevity, we say that an m-configuration with cost at most a  OPT k is an (m, a)-configuration.
A k-median algorithm is (m, a)-approximate if it produces an (m, a)-configuration. A k-median
algorithm is a-approximate if it is (k, a)-approximate. Let R d denote the ratio of the diameter of
U (i.e., the maximum distance between any pair of points in U ) to the minimum distance between
any pair of distinct points in U . Let Rw denote the ratio of the maximum weight of any point in
U to the minimum nonzero weight of any point in U . (Remark: We can assume without loss of
generality that at least one point in U has nonzero weight since the problem is trivial otherwise.)
Let r
Our main result is a randomized O(1)-approximate k-median algorithm that runs in O(nk) time
subject to the constraints k
O(n). The algorithm
succeeds with high probability, that is, for any positive constant , we can adjust constant factors
in the definition of the algorithm to achieve a failure probability less than n  . We establish a
matching
lower bound on the running time of any randomized O(1)-approximate k-median
algorithm with a nonnegligible success probability (e.g., at least 1), subject to the requirement
that R d exceeds n=k by a sufficiently large constant factor relative to the desired approximation
ratio. To obtain tight bounds for the clustering variant, we also prove an
time lower bound
for any O(1)-approximate algorithm, but we only require that R d be a sufficiently large constant
relative to the desired approximation ratio. Additionally, our lower bounds assume only that
O(1).
Our main technical result is a successive sampling technique that we use in all of our algo-
rithms. The basic idea behind the technique is to take a random sample of the points, set aside a
constant fraction of the n points that are "close" to the sample, and recurse on the remaining points.
We show that this technique rapidly produces a configuration whose cost is within a constant factor
of optimal. Specifically, for the case of uniform weights, our successive sampling algorithm yields
a (k log (n=k), O(1))-configuration with high probability in O(nmaxfk; log ng) time.
In addition to this sampling result, our algorithms rely on an extraction technique due to Guha
et al. [5] that uses a black box O(1)-approximate k-median algorithm to compute a (k, O(1))-
configuration from any (m, O(1))-assignment. The black box algorithm that we use is the linear-time
deterministic online median algorithm of Mettu and Plaxton [10].
In developing our randomized algorithm for the k-median problem we first consider the special
case of uniform weights, that is, where 1. For this special case we provide a randomized
algorithm running in O(nmaxfk; log ng) time subject to the constraint r d log n
O(n). The
uniform-weights algorithm is based directly on the two building blocks discussed above: We apply
the successive sampling algorithm to obtain (k log (n=k), O(1))-configuration and then use the
extraction technique to obtain a (k, O(1))-configuration. We then use this algorithm to develop
a k-median algorithm for the case of arbitrary weights. Our algorithm begins by partitioning the
points into r w power-of-2 weight classes and applying the uniform-weights algorithm within
each weight class (i.e., we ignore the differences between weights belonging to the same weight
class, which are less than a factor of 2 apart). The union of the r w k-configurations thus obtained
is an (r w k, O(1))-configuration. We then make use of our extraction technique to obtain a (k,
O(1))-configuration from this (r w k, O(1))-configuration.
1.1 Problem Definitions
Without loss of generality, throughout this paper we consider a fixed set of n points, U , with an
associated distance function d : U  U ! IR and an associated nonnegative demand function
We assume that d is a metric, that is, d is nonnegative, symmetric, satisfies the
triangle inequality, and d(x; y. For a configuration X and a set of points Y , we let
cost
For any set of points X , we let w(X) denote  x2X w(x).
We define an assignment as a function from U to U . For any assignment  , we let (U) denote
the set f(x) j x 2 Ug. We refer to an assignment  with j (U)j  m as a m-assignment.
Given an assignment  , we define the cost of  , denoted c (), as
w(x). It is
straighforward to see that for any assignment  , cost ((U))  c (). For brevity, we say that
an assignment  with j (U)j  m and cost at most a  OPT k is an (m, a)-assignment. For an
assignment  and a set of points X , we let c (;
The input to the k-median problem is (U; d; w) and an integer k, 0 < k  n. Since our goal is
to obtain a (k, O(1))-configuration, we can assume without loss of generality that all input points
have nonzero weight. We note that for all m, 0 < m  n, removing zero weight points from
an m-configuration at most doubles its cost. To see this, consider an m-configuration X; we can
obtain an m-configuration X 0 by replacing each zero weight point with its closest nonzero weight
point. Using the triangle inequality, it is straightforward to see that cost (X 0 )  2cost (X). This
argument can be used to show that any minimum-cost set of size m contained in the set of nonzero
weight input points has cost at most twice OPT m . We also assume that the input weights are scaled
such that the smallest weight is 1; thus the input weights lie in the range [1; Rw ]. For output, the
k-median problem requires us to compute a minimum-cost k-configuration. The uniform weights
k-median problem is the special case in which w(x) is a fixed real for all points x. The output is
also a minimum-cost k-configuration.
1.2 Comparison to Previous Work
The first O(1)-approximate k-median algorithm was given by Charikar et al. [3]. Subsequently,
there have been several improvements to the approximation ratio (see, e.g., [2] for results and ci-
tations). In this section, we focus on the results that are most relevant to the present paper; we
compare our results with other recent sublinear-time algorithms for the k-median problem. The
first of these results is due to Indyk, who gives a randomized (O(k), O(1))-approximate algorithm
for the uniform weights k-median problem [6]. Indyk's algorithm combines random sampling
of the input points with a black-box (k, )-approximate k-median algorithm to achieve a
((1+)(6+3)k, 2)-approximate algorithm, where  is the desired success probability. Given an
~
O(n 2 )-time 1 black-box k-median algorithm, Indyk's algorithm runs in ~
factor in the running time
is
26 2 k).) Indyk's algorithm takes O(
nk log
points and then runs the black-box k-median algorithm on those points to obtain a configuration
. The black-box algorithm is then run again on a set of points that are distant from points in X
to produce another configuration Y . The final output is the union of X and Y , which is shown to
be an (O(k), O(1))-configuration.
Thorup [13] gives a randomized O(1)-approximate algorithms for the k-median, k-center, and
1 The ~
O-notation omits polylogarithmic factors in n and k.
facility location problems in a graph. For these problems, we are not given a metric distance
function but rather a graph on the input points with m positively weighted edges from which
the distances must be computed; all of the algorithms in [13] run in ~
O(m) time. Thorup [13]
also gives an ~
randomized constant-factor approximation algorithm for the k-median
problem that we consider. (The polylogarithmic factor in the running time
is
44 4 n).) As part
of this k-median algorithm, Thorup gives a successive sampling technique that also consists of a
series of sampling steps but produces an (O((k log 2 n)="), ")-configuration for any positive
real " with 0 < " < 0:4 with probability 1=2.
Our successive sampling technique is similar in spirit to both of the above algorithms, but we
take a total of O(log (n=k)) samples, each of size O(k), and construct an (O(k log (n=k), O(1))-
assignment from the union of the samples. Overall, our sample size is much smaller than in Indyk's
algorithm (O(k log (n=k)) points versus O(
nk log smaller than the sample size in
Thorup's algorithm by a logarithmic factor. However, our algorithm produces an (O(k log (n=k),
O(1))-assignment whereas Indyk's algorithm produces an (O(k), O(1))-configuration. Addition-
ally, the algorithms of Indyk and Thorup both succeed with a constant probability, while our sampling
algorithm is guaranteed to succeed with high probability.
Guha et al. [5] give k-median algorithms for the data stream model of computation. Under the
data stream model of computation, input data is processed sequentially, and the performance of an
algorithm is measured by how many passes it makes over the input and by its space requirements.
Guha et al. [5] give a single-pass O(1)-approximate algorithm for the k-median problem that runs
in ~
time and requires O(n " ) space for a positive constant ". (Their algorithm uses Indyk's
k-median algorithm as a black box and hence the polylogarithmic factor in the running time is also
Mishra et al. [11] show that in order to find a (k, O(1))-configuration, it is enough to take a
sufficiently large sample of the input points and use it as input to a black-box O(1)-approximate
k-median algorithm. To compute a (k, O(1))-configuration with an arbitrarily high constant prob-
ability, the required sample size is ~
d k). The running time of this technique depends on the
black-box algorithm used. In the general case, the size of the sample may be as large as n, but
depending on the diameter of the input metric space, this technique can yield running times of
the diameter is o(n 2 =k)).
As noted earlier, we also make use of a technique due to Guha et al. [5] that takes an (m,
O(1))-configuration and extracts a (k, O(1))-configuration; they use this technique in isolation
in a divide-and-conquer fashion to develop their k-median algorithms. We view the extraction
technique as a postprocessing step that yields a (k, O(1))-approximate k-median algorithm given
an (m, O(1))-approximate k-median algorithm. In our algorithms, we take advantage of the fact
that this postprocessing step can be performed rapidly. For example, if and the black-box
algorithm requires O(n 2 ) time, the time required for postprocessing is just O(k 2 ).
Guha et al. [5] establish a lower bound of
for deterministic O(1)-approximate k-median
algorithms. We note that they work with a slightly different definition of the k-median problem in
which the distance between two distinct points is allowed to be 0. We adopt the view that points
at distance zero are represented by a single point with commensurately higher weight; this view
avoids having an infinite value for R d . For the proof of the lower bound, Guha et al. [5] construct
a problem instance for which optimal solution has cost 0 and reduce the problem to a graph k-
partitioning problem [7]. The intuition is that any algorithm producing a k-configuration with
nonzero cost is not O(1)-approximate. Although their problem instance contains distinct points at
distance 0 (i.e., an infinite R d ), with a slight modification their proof only requires that R d exceed
n by a sufficiently large constant factor relative to the desired approximation ratio. Intuitively, with
such a large setting of R d , a deterministic k-median algorithm taking o(nk) time and making just
one "mistake" has fails to achieve the desired approximation ratio. Our lower bounds are stronger
in the sense that we focus on constructing problem instances that have small values of R d , and
then show that any randomized k-median algorithms running in o(nk) time is likely to make many
"mistakes" on these instances.
1.3 Outline
The rest of this paper is organized as follows. In Section 2, we present and analyze our successive
sampling algorithm. In Section 3, we make use of our sampling algorithm, in conjunction with an
extraction result, to develop an O(1)-approximate uniform weights k-median algorithm. Then, in
Section 4, we use the uniform weights algorithm as a subroutine to develop an O(1)-approximate
k-median algorithm for the case of arbitrary weights. We present our lower bounds for the k-median
problem and its clustering variant in Appendix A.
Approximate Clustering via Successive Sampling
Our first result is a successive sampling algorithm that constructs an assignment that has cost
probability. We make use of this algorithm to develop our uniform weights
k-median algorithm. (Remark: We assume arbitrary weights for our proofs since the arguments
generalize easily to the weighted case; furthermore, the weighted result may be of independent
Informally speaking, the algorithm works in sampling steps. In each step we take a small
sample of the points, set aside a constant fraction the weight whose constituent points are each
close to the sample, and recurse on the remaining points. Since we eliminate a constant fraction of
the weight at each sampling step, the number of samples taken is logarithmic in the total weight.
We are able to show that using the samples taken, it is possible to construct an assignment whose
cost is within a constant factor of optimal with high probability. For the uniform weights k-median
problem, our sampling algorithm runs in O(nmaxfk; log ng) time. (We give a k-median algorithm
for the case of arbitrary weights in Section 4.)
Throughout this section, we use the symbols , , and k 0 to denote real numbers appearing in
the definition and analysis of our successive sampling algorithm. The value of  and k 0 should be
chosen to ensure that the failure probability of the algorithm meets the desired threshold. (See the
paragraph preceding Lemma 2.3 for discussion of the choice of  and k 0 .) The asymptotic bounds
established in this paper are valid for any choice of  such that 0 <  < 1.
We also make use of the following definitions:
A ball A is a pair (x; r), where the center x of A belongs to U , and the radius r of A is a
nonnegative real.
Given a ball A = (x; r), we let Points(A) denote the set fy 2 U j d(x; y)  rg. However,
for the sake of brevity, we tend to write A instead of Points(A). For example, we write "x 2
A" and "A [ B" instead of "x 2 Points(A)" and "Points(A) [ Points(B)", respectively.
For any set X and nonnegative real r, we define Balls(X; r) as the set [ x2X A x where A
r).
2.1 Algorithm
The following algorithm takes as input an instance of the k-median problem and produces an
assignment  such that with high probability, c O(cost (X)) for any k-configuration X .
Construct a set of points S i by sampling (with replacement) bk 0 c times from U i , where at
each sampling step the probability of selecting a given point is proportional to its weight.
For each point in U i , compute the distance to the nearest point in S i .
Using linear-time selection on the distances computed in the previous step, compute the
smallest real  i such that w(Balls(S
For each x in C i , choose a point y in S i such that d(x; y)   i and let y.
Let U
Note that the loop terminates since w(U i ) < w(U i+1 ) for all i  0. Let t be the total number
of iterations of the loop. Let C . By the choice of C i in each iteration and the loop
termination condition, t is O(log (w(U)=k 0 )). For the uniform demands k-median problem, t is
simply O(log (n=k 0 )). From the first step it follows that j(U)j is O(tk 0 ).
The first step of the algorithm can be performed in O(nk 0 iterations. In each
iteration the second and third steps can be performed in time O(jU using a (weighted) linear
time selection algorithm. For the uniform demands k-median problem, this computation requires
iterations. The running times of the third and fourth steps are negligible.
Thus, for the uniform demands k-median problem, the total running time of the above algorithm is
O(nk
2.2 Approximation Bound
The goal of this section is to establish Theorem 1. The proof of the theorem makes use of Lemmas
2.3, 2.5, and 2.11, which are established below. We remark that Theorem 1 is used in Sections 3
and 4.
Theorem 1 With high probability, c O(cost (X)) for any k-configuration X .
Proof: The claim of Lemma 2.3 holds with high probability if we set k log ng and
and  appropriately large. The theorem then follows from Lemmas 2.3, 2.5, and 2.11.
The proof of Lemma 2.3 below relies on bounding the failure probability of a certain family of
random experiments. We begin by bounding the failure probability of a simpler family of random
experiments related to the well-known coupon collector problem. For any positive integer m and
any nonnegative reals a and b, let us define f(m; a; b) as the probability that more than am bins
remain empty after dbe balls are thrown at random (uniformly and independently) into m bins.
Techniques for analyzing the coupon collector problem (see. e.g., [12]) can be used to obtain sharp
estimates on f(m; a; b). However, the following simple upper bound is sufficient for our purposes.
Lemma 2.1 For any positive real ", there exists a positive real  such that for all positive integers
m and any real b  m, we have f(m; "; b)  e b .
Proof: Note that a crude upper bound on f(m; "; b) is given by the probability of obtaining
at most (1 ")m successes in dbe Bernoulli trials, each of which has success probability ".
The claim then follows by choosing  sufficiently large and applying a standard Chernoff bound.
(We have in mind the following tail bound: If X is a random variable drawn from a Bernoulli
distribution with n trials and each trial has success probability p, then for all  such that 0    1,
Pr fX  (1 )npg  e  2 np=2 ; see [1, Appendix A] for a derivation.)
We now develop a weighted generalization of the preceding lemma. For any positive integer
m, nonnegative reals a and b, and m-vector nonnegative reals r i , we define
define g(m; a; b; v) as follows. Consider a set of m bins numbered from 0 to m 1 where bin i
has associated weight r i . Let R denote the total weight of the bins. Assume that each of dbe balls
is thrown independently at random into one of the m bins, where bin i is chosen with probability
m. We define g(m; a; b; v) as the probability that the total weight of the empty bins
after all of the balls have been thrown is more than aR.
Lemma 2.2 For any positive real " there exists a positive real  such that for all positive integers
m and any real b  m, we have g(m; "; b; v)  e b for all m-vectors v of nonnegative reals.
Proof: Fix ", b, m, and v. We will use Lemma 2.1 to deduce the existence of a suitable choice of
that depends only on ". Our strategy for reducing the claim to its unweighted counterpart will be
to partition almost all of the weight associated with the m weighted bins into (m) "sub-bins" of
equal weight. Specifically, we let s denote "R
and for each i we partition the weight r i associated
with bin i into
s
complete sub-bins of weight s and one incomplete sub-bin of weight less than
s. Furthermore, when a ball is thrown into a particular bin, we imagine that the throw is further
refined to a particular sub-bin of that bin, where the probability that a particular sub-bin is chosen
is proportional to its weight.
Note that the total weight of the incomplete sub-bins is less than "R=2. Furthermore, we can
assume without loss of generality that "  1, since the claim holds vacuously for " > 1. It
follows that less than half of the total weight R lies in incomplete sub-bins. Thus, by a standard
Chernoff bound argument, for any positive real  0 we can choose  sufficiently large to ensure that
the following claim holds with probability of failure at most e b =2 (i.e., half the desired failure
threshold appearing in the statement of the lemma): At least  0 b of the dbe balls are thrown into
complete sub-bins.
the number of complete sub-bins. Since at least half of the total weight R
belongs to complete sub-bins, we have m="  m 0  2m=". Accordingly, by a suitable application
of Lemma 2.1, we can establish the existence of a positive real  0 (depending only on ") such that,
after at least  0 b balls have landed in complete sub-bins, the probability that the number of empty
complete sub-bins exceeds "m 0 =2 is at most e b =2.
From the claims of the two preceding paragraphs, we can conclude that there exists a  (de-
pending only on ") such that the following statement holds with probability of failure at most e b :
The number of empty complete sub-bins is at most "m 0 =2. Note that the total weight of the complete
sub-bins is at most s  " 2t
As argued earlier, the total weight of the incomplete
sub-bins is also at most "R=2. Thus, there exists a positive real  such that after dbe ball tosses,
the probability that the total weight of the empty bins is more than "R is at most e b .
For the remainder of this section, we fix a positive real
such that  <
< 1. We also
let  i denote the minimum real such that there exists a k-configuration X with the property that
w(U below establishes the main probabilistic claim used in our
analysis of the algorithm of Section 2.1. We note that the lemma holds with high probability by
taking neg and  and  appropriately large.
Lemma 2.3 For any positive real , there exists a sufficiently large choice of  such that  i  2 i
for all i, 0  i  t, with probability of failure at most e k 0
Proof: Fix i and let X denote a k-configuration such that w(Balls(X;  i
w(U us
define each point y in U i to be good if it belongs to Balls(X;  i ), and bad otherwise. Let G denote
the set of good points. We associate each good point y with its closest point in X , breaking ties
arbitrarily. For each point x in X , let A x denote the set of good points associated with x; note that
the sets A x form a partition of G. Recall that S i denotes the ith set of sample points chosen by the
algorithm. For any x in X , we say that covers A x iff S i \ A x is nonempty. For any point y, we
say that covers y iff there exists an x in X such that y belongs to A x and S i covers A x . Let G 0
denote the set of points covered by S i ; note that G 0  G.
We will establish the lemma by proving the following claim: For any positive reals " and ,
there exists a sufficiently large choice of  such that w(G 0 )  (1 ")w(G) with probability of
failure at most e k 0
. This claim then implies the lemma because  (the factor appearing in the
definition of  i ) is less than
(the factor appearing in the definition of  i ) and for all points y
covered by S i ,
It remains to prove the preceding claim. First, note that the definition of  i implies that at least
a
fraction of the total weight is associated with good points. Thus, a standard Chernoff bound
argument implies that for any positive reals  and , there exists a sufficiently large choice of
such that at least k 0 of the bk 0 c samples associated with the construction of S i are good with
probability of failure at most e k 0
=2.
To ensure that w(G 0 ) is at least (1 ")w(G) with failure probability e k 0
=2, we can apply
Lemma 2.2 by viewing each sample associated with a good point in S i as a ball toss and each set
A x as a bin with weight w(A x ). The claim then follows.
Lemma 2.4 For all i such that 0  i  t, c (; C
Proof: Observe that
where the second step follows from the definition of C i and the construction of (x).
0it
Proof: Observe that
0it
0it
The first step follows since the sets C i , 0  i  t, form a partition of U . The second step follows
from Lemma 2.4.
Throughout the remainder of this section we fix an arbitrary k-configuration X . For all i such
that 0  i  t, we let F i denote the set fx 2 U g, and for any integer m > 0, we
Lemma 2.6 Let i, j, and m be integers such that 0  i  t, 0  j  t, m > 0, and (i
Proof: Without loss of generality, assume that i < j. Then, by definition, F m
j do not intersect.
Lemma 2.7 Let i be an integer such that 0  i  t and let Y be a subset of F i . Then w(F
cost (X; Y )   i w(Y ).
Proof: First, note that by the definition of  i , w(F i ) is at least (1
By the definition of
any y in F i . Thus cost (X; Y
Lemma 2.8 For all i, j, and m such that 0  i  t, 0  j  t, and m > 0,
cost
(i
Proof: By Lemma 2.6, for all i, j, and m such that 0  i  t,0  j  t, and m > 0,
cost
(i
cost
By Lemma 2.7, cost (X; F m
i ), and the claim follows.
For the remainder of the section, let
)=3)e.
Lemma 2.9 For all i such that 0  i  t, w(F i+r )  1w(F i ).
Proof: Note that w(F i+r
last step
follows from Lemma 2.7. The claim then follows by the definition of r.
Lemma 2.10 For all i such that 0  i  t, w(F r
w(F r
where the second step follows from Lemma 2.9.
Lemma 2.11 For any k-configuration X ,
cost (X)
0it
(i
i )g and fix a k-configuration X . Then cost (X)
is at least
cost
(i
r
0it
0it
0it
0it
where the first step follows from Lemma 2.8, the second step follows from averaging and the
choice of j, the third step follows from Lemma 2.10, the fourth step follows from Lemma 2.7, and
the last step follows since C i  U .
3 An Efficient Algorithm for the Case of Uniform Weights
Theorem 2.4 of Guha et al. [5] implies that for any given (m, O(1))-configuration X , we can
compute a (k, O(1))-configuration by simply running an O(1)-approximate k-median algorithm
on the modified problem instance obtained by redistributing the point weights as follows: The
weight of any given point x is moved to a point y in X such that d(x;
follows from the analysis of algorithm Small-Space of Guha et al. [5], since it corresponds to the
case in which and the (m, O(1))-configuration is the output in step 2. It should be
remarked that although algorithm Small-Space is presented in a manner that assumes the output
of step 2 to be ' (O(k), O(1))-configurations, the analysis of Small-Space given in [5] is easily
seen to hold for the more general case in which the output of step 2 is a collection of ' (m, O(1))-
configurations.)
By Theorem 1, the output of our sampling algorithm is an (m, O(1))-assignment with high
probability, where ng log (n=k)) in the case of uniform weights. Thus (U)
is an (m, O(1))-configuration with high probability, and we can directly apply the Guha et al. [5]
technique to extract a (k, O(1))-configuration from (U). The only trouble with this approach is
that a direct application of their technique expends in computing the closest
point in (U) to each point in U . Fortunately, it is straightforward to verify that the following
variation of the Guha et al. [5] technique is also valid. Given an (m, O(1))-assignment, we can
redistribute the weight of each point x to (x) and then run an O(1)-approximate k-median algorithm
on the modified problem instance. (Remark: In [5, Section 2], the point i 0 is defined to be
the median closest to the point i. For the purposes of our variation, the point i 0 should instead be
defined as (i). )
We now analyze the running time of the above algorithm. To compute the assignment , we
use our sampling algorithm with the parameter k 0 set to O(maxfk; log ng). The time required to
compute  is then O(nmaxfk; log ng). We note that the required weight function can be computed
during the execution of the sampling algorithm without increasing its running time. The
deterministic online median algorithm of Mettu and Plaxton [10] can then be used to complete the
extraction step in O(j(U)j 2 time. The total time taken by the algorithm is therefore
where the first step follows from the analysis of our sampling algorithm for the case of uniform
weights. By the choice of k 0 , the overall running time is O((n log (n=k)) maxfk; log ng).
Note that if k
148 n) and kr 2
simplifies to O(nk).
4 An Efficient Algorithm for the Case of Arbitrary Weights
The algorithm developed in Sections 2 and 3 is O(1)-approximate for the k-median problem with
arbitrary weights. However, the time bound established for the case of uniform weights does
not apply to the case of arbitrary weights because the running time of the successive sampling
procedure is slightly higher in the latter case. (More precisely, the running time of the sampling
algorithm of Section 2 is O(nk 0 log w(U)
for the case of arbitrary weights.) In this section, we
use the uniform-weight algorithm developed in Sections 2 and 3 to develop a k-median algorithm
for the case of arbitrary weights that is time optimal for a certain range of k.
We first give an informal description of the algorithm, which consists of three main steps. First,
we partition the input points according to weight into r w sets. Next, we run our uniform weights
k-median algorithm on each of the resulting sets, and show that the union of the resulting outputs is
an (O(krw ), O(1))-configuration. We then obtain a (k, O(1))-configuration by creating a problem
instance from the (O(krw ), O(1))-configuration computed in the previous step and then feeding
this problem instance as input to an O(1)-approximate k-median algorithm.
We now give a more precise description of our k-median algorithm. Let A be the uniform
weights k-median algorithm of Sections 2 and 3, and let B be an O(1)-approximate k-median
algorithm.
Compute such that for all x
For as the set of input points, d as the distance function,
as the fixed weight, and the parameter k denote the output.
Let  i denote the assignment induced by Z i , that is,
y). For a point x, if x 2 Z i , let ~
Let  be the assignment corresponding to the union of the assignments  i defined in the
previous step, and let ~
w  denote the weight function corresponding to the union of the weight
functions ~
. Run B with (U) as the set of input points, d as the distance function, and ~
as the weight function. Output the resulting k-configuration.
Note that in the second step, k 0 is defined in terms of n (i.e., jU j) and not jB i j. Thus, the
argument of the proof of Theorem 1 implies that A succeeds with high probability in terms of
n. Assuming that r w is polynomially bounded in n, with high probability we have that every
invocation of A is successful.
We now observe that the above algorithm corresponds to the special case of algorithm Small-
Space of [5] in which the parameter ' is set to r w , the uniform weights algorithm of Section 3 is
used in step 2 of Small-Space, and the online median algorithm of [10] is used in step 4 of Small-
Space. Thus, [5, Theorem 2.4] implies that the output of B is a (k, O(1))-configuration with high
probability.
We now discuss the running time of the above algorithm. It is straightforward to compute the
sets B i in O(n) time. Our uniform weights k-median algorithm requires O((jB
time to compute Z i , so the time required for all invocations of A is

r w

nk 0
r w
kr w
!!
O
kr w
(The first step follows from the fact that the sum is maximized when jB .) Note that each
weight function ~
can be computed in O(jB i j
w  can be computed in
time. We employ the online median algorithm of [10] as the black-box k-median algorithm
B. Since j(U)j is at most kr w , the time required for the invocation of B is O((krw
time required for our k-median algorithm is therefore O((n
kr w r d ). Note that if k
197 n), kr 2
krw
simplifies to O(nk).



--R

The Probabilistic Method.
Improved combinatorial algorithms for facility location and k-median problems

Pattern Classification and Scene Analysis.
Clustering data streams.
time algorithms for metric space problems.
Randomized query processing in robot path planning.
Lower bounds for randomized exclusive write PRAMs.
Foundations of Statistical Natural Language Processing.
The online median problem.
clustering.
Randomized Algorithms.
Quick k-medians
Probabilistic computations: Toward a unified measure of complexity.
--TR
Randomized algorithms
A constant-factor approximation algorithm for the <italic>k</italic>-median problem (extended abstract)
time algorithms for metric space problems
Foundations of statistical natural language processing
Sublinear time approximate clustering
Learning mixtures of arbitrary gaussians
A new greedy approach for facility location problems
Quick k-Median, k-Center, and Facility Location for Sparse Graphs
The Online Median Problem
Improved Combinatorial Algorithms for the Facility Location and k-Median Problems
Learning Mixtures of Gaussians
Clustering data streams
Pattern Classification (2nd Edition)
Approximation algorithms for np -hard clustering problems

--CTR
Shai Ben-David, A framework for statistical clustering with constant time approximation algorithms for K-median and K-means clustering, Machine Learning, v.66 n.2-3, p.243-257, March     2007
Kobbi Nissim , Sofya Raskhodnikova , Adam Smith, Smooth sensitivity and sampling in private data analysis, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
C. Greg Plaxton, Approximation algorithms for hierarchical location problems, Journal of Computer and System Sciences, v.72 n.3, p.425-443, May 2006
Dan Feldman , Morteza Monemizadeh , Christian Sohler, A PTAS for k-means clustering based on weak coresets, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
Gereon Frahling , Christian Sohler, A fast k-means implementation using coresets, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
k-median;discrete location theory;approximation algorithms;unsupervised clustering;k-means