Approximate Clustering via Metric Partitioning∗
Sayan Bandyapadhyay† and Kasturi Varadarajan‡
Department of Computer Science
University of Iowa, Iowa City, USA

arXiv:1507.02222v3 [cs.CG] 3 Oct 2016

Abstract
In this paper we consider two metric covering/clustering problems - Minimum Cost Covering
Problem (MCC) and k-clustering. In the MCC problem, we are given two point sets X (clients)
and Y (servers), and a metric on X ∪ Y . We would like to cover the clients by balls centered at
the servers. The objective function to minimize is the sum of the α-th power of the radii of the
balls. Here α ≥ 1 is a parameter of the problem (but not of a problem instance). MCC is closely
related to the k-clustering problem. The main difference between k-clustering and MCC is that
in k-clustering one needs to select k balls to cover the clients.
For any ε > 0, we describe quasi-polynomial time (1 + ε) approximation algorithms for both
of the problems. However, in case of k-clustering the algorithm uses (1 + ε)k balls. Prior to
our work, a 3α and a cα approximation were achieved by polynomial-time algorithms for MCC
and k-clustering, respectively, where c > 1 is an absolute constant. These two problems are thus
interesting examples of metric covering/clustering problems that admit (1 + ε)-approximation
(using (1 + ε)k balls in case of k-clustering), if one is willing to settle for quasi-polynomial time.
In contrast, for the variant of MCC where α is part of the input, we show under standard
assumptions that no polynomial time algorithm can achieve an approximation factor better than
O(log |X|) for α ≥ log |X|.
1998 ACM Subject Classification I.3.5 Computational Geometry and Object Modeling
Keywords and phrases Approximation Algorithms, Clustering, Covering, Probabilistic Partitions
Digital Object Identifier 10.4230/LIPIcs...

1

Introduction

We consider two metric covering/clustering problems. In the first problem, we are given two
point sets X (clients) and Y (servers), and a metric d on X ∪ Y . For z ∈ X ∪ Y and r ≥ 0,
the ball B(z, r) centered at z and having radius r ≥ 0 is the set {y ∈ X ∪ Y |d(z, y) ≤ r}.
A cover for a subset P ⊆ X is a set of balls, each centered at a point of Y , whose union
Pk
α
contains P . The cost of a set B = {B1 , . . . , Bk } of balls, denoted by cost(B), is i=1 r(Bi ) ,
where r(Bi ) is the radius of Bi , and α ≥ 1 is a parameter of the problem (but not of a
problem instance). The goal is to compute a minimum cost cover for the clients X. We refer
to this problem as the Minimum Cost Covering Problem (MCC).
In the second problem, we are given a set X of n points, a metric d on X, and a positive
integer k. Unlike in the case of MCC, here each ball is centered at a point in X.1 The cost

∗
†
‡
1

This material is based upon work supported by the National Science Foundation under Grant CCF1318996
sayan-bandyapadhyay@uiowa.edu
kasturi-varadarajan@uiowa.edu
Our results do generalize to the problem where we distinguish between clients and servers as in the
MCC.
© Sayan Bandyapadhyay and Kasturi Varadarajan;
licensed under Creative Commons License CC-BY
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

XX:2

Approximate Clustering via Metric Partitioning

cost(B) of a set B of balls is defined exactly in the same way as in the case of MCC. The
goal is to find a set B of k balls whose union contains all the points in X and cost(B) is
minimized. We refer to this problem as k-clustering.
Inspired by applications in wireless networks, MCC has been well studied [21]. One can
consider the points in Y as the potential locations of mobile towers and the points in X
as the locations of customers. A tower can be configured in a way so that it can serve the
customers lying within a certain distance. But the service cost increases with the distance
served. The goal is to serve all the customers minimizing the total cost. For modelling the
energy needed for wireless transmission, it is common to consider the value of α to be at
least 1.
For the MCC problem with α = 1, a primal-dual algorithm of Charikar and Panigrahy
[9] leads to an approximation guarantee of 3; their result generalizes to α ≥ 1, with an
approximation guarantee of 3α . The problem is known to be NP-hard for α > 1, even when
X and Y are points in the Euclidean plane [2]. The case α = 1 has received particular
attention. The first PTAS for the Euclidean plane was designed by Lev-Tov and Peleg
[21]. Later, Gibson et. al [16] have designed a polynomial time exact algorithm for this
problem when X and Y are points in the plane, and the underlying distance function d is
either the l1 or l∞ metric. For the l2 metric they also get an exact algorithm if one assumes
two candidate solutions can be compared efficiently; without this assumption, they get a
(1 + ε) approximation. Their algorithm is based on a separator theorem that, for any optimal
solution, proves the existence of a balanced separator that intersects with at most 12 balls in
the solution. In a different work they have also extended the exact algorithm to arbitrary
metric spaces [15]. The running time is quasi-polynomial if the aspect ratio of the metric
(ratio of maximum to minimum interpoint distance) is bounded by a polynomial in the
number of points. When the aspect ratio is not polynomially bounded, they obtain a (1 + ε)
approximation in quasi-polynomial time. Their algorithms are based on a partitioning of the
metric space that intersects a small number of balls in the optimal cover.
When α > 1, the structure that holds for α = 1 breaks down. It is no longer the case,
even in the Euclidean plane, that there is a good separator (or partition) that intersects
a small number of balls in an optimal solution. In the case α = 2 and the Euclidean
plane, the objective function models the total area of the served region, which arises in
many practical applications. Hence this particular version has been studied in a series of
works. Chuzhoy developed an unpublished 9-factor approximation algorithm for this version.
Freund and Rawitz [14] present this algorithm and give a primal fitting interpretation of the
approximation factor. Bilo et. al [8] have extended the techniques of Lev-Tov and Peleg [21]
to get a PTAS that works for any α ≥ 1 and for any fixed dimensional Euclidean space. The
PTAS is based on a sophisticated use of the shifting strategy which is a popular technique in
computational geometry for solving problems in Rd [12, 18]. For general metrics, however,
the best known approximation guarantee for α > 1 remains the already mentioned 3α [9].
The k-clustering problem has applications in many fields including Data Mining, Machine
Learning and Image Processing. Over the years it has been studied extensively from both
theoretical and practical perspectives [8, 9, 11, 15, 16, 22]. The problem can be seen as a
variant of MCC where Y = X and at most k balls can be chosen to cover the points in X.
As one might think, the constraint on the number of balls that can be used in k-clustering
makes it relatively harder than MCC. Thus all the hardness results for MCC also hold for
k-clustering. For α = 1, Charikar and Panigrahy [9] present a polynomial time algorithm with
an approximation guarantee of about 3.504. Gibson et. al [15, 16] obtain the same results
for k-clustering with α = 1 as the ones described for MCC, both in Rd and arbitrary metrics.

S. Bandyapadhyay and K. Varadarajan

Recently, Salavatipour and Behsaz [7] have obtained a polynomial time exact algorithm for
α = 1 and metrics of unweighted graphs, if we assume that no singleton clusters are allowed.
However, in case of α > 1 the best known approximation factor (in polynomial time) for
general metrics is cα , for some absolute constant c > 1; this follows from the analysis of
Charikar and Panigrahy [9], who explicitly study only the case α = 1. In fact, no better
polynomial time approximation is known even for the Euclidean plane. We note that though
the polynomial time algorithm in [8] yields a (1 + ε) approximation for k-clustering in any
fixed dimensional Euclidean space and for α ≥ 1, it can use (1 + ε)k balls.
In addition to k-clustering many other clustering problems (k-means, k-center, k-median
etc.) have been well studied [4, 10, 23, 17].
In this paper we address the following interesting question. Can the techniques employed
by [8] for fixed dimensional Euclidean spaces be generalized to give (1 + ε) approximation
for MCC and k-clustering in any metric space? Our motivation for studying the problems
in a metric context is partly that it includes two geometric contexts: (a) high dimensional
Euclidean spaces; and (b) shortest path distance metric in the presence of polyhedral obstacles
in R2 or R3 .

1.1

Our Results and Techniques

In this paper we consider the metric MCC and k-clustering with α ≥ 1. For any  > 0, we
design a (1 + )-factor approximation algorithm for MCC that runs in quasi-polynomial time,
c
that is, in 2(log mn/ε) time, where c > 0 is a constant, m = |Y |, and n = |X|. We also have
designed a similar algorithm for k-clustering that uses at most (1 + ε)k balls and yields a
solution whose cost is at most (1 + ε) times the cost of an optimal k-clustering solution. The
time complexity of the latter algorithm is also quasi-polynomial. As already noted, somewhat
stronger guarantees are already known for the case α = 1 of these problems [15], but the
structural properties that hold for α = 1 make it rather special.
The results in this paper should be compared with the polynomial time algorithms [9]
that guarantee 3α approximation for MCC and cα approximation for k-clustering. The MCC
and k-clustering are thus interesting examples of metric covering/clustering problems that
admit (1 + ε)-approximation (using (1 + ε)k balls in case of k-clustering), if one is willing to
settle for quasi-polynomial time. From this perspective, our results are surprising, as most of
the problems in general metrics are APX-hard. The MCC and k-clustering are also examples
where the techniques used in fixed dimensional Euclidean spaces generalize nicely to metric
spaces. This is in contrast to the facility location problem [3].
The algorithms that we have designed for both of the problems use similar techniques
that exploit the following key property of optimal covers: there are only a “small” number
of balls whose radius is “large”. We can therefore afford to guess these balls by an explicit
enumeration. However, there can be a “large” number of balls with “small” radius. To help
‘find’ these, we partition the metric space into blocks (or subsets) with at most half the
original diameter, and recurse on each block. We have to pay a price for this recursion in the
approximation guarantee. This price depends on the number of blocks in the partition that
a small radius ball can intersect. (This is not an issue in the case α = 1, where each ball
that is not guessed intersects precisely one of the blocks [15].)
We are led to the following problem: is there a way to probabilistically partition a metric
space into blocks of at most half the diameter, so that for any ball with “small” radius, the
expected number of blocks that intersect the ball can be nicely bounded? The celebrated
partitioning algorithms of Bartal [5] and Fakcharoenphol, Rao, and Talwar [13] guarantee
that the probability that such a ball is intersected by two or more blocks is nicely bounded.

XX:3

XX:4

Approximate Clustering via Metric Partitioning

However, their bounds on the probability that a small ball is intersected do not directly
imply a good bound on the expected number of blocks intersected by a small ball. Indeed, if
one employs the partitioning algorithm of [13], the expected number of blocks intersected
by a small ball can be quite “large”. Fortunately, the desired bound on the expectation
can be shown to hold for the algorithm of Bartal [5], even though he did not study the
expectation itself. We use a similar partitioning scheme and derive the expectation bound in
Section 2, using an analysis that closely tracks previous work [1, 6, 19]. While the bound
on the expectation is easily derived from previous work, our work is the first to study and
fruitfully apply this bound.
The algorithms for MCC and k-clustering, which use the partitioning scheme of Section 2,
are described in Section 3 and 4, respectively. In Section 5, we consider the approximability
of a variant of the MCC where we allow α to be part of the input. For α ≥ log |X|, we show,
under standard complexity theoretic assumptions, that no polynomial (or quasi-polynomial)
time algorithm for MCC can achieve an approximation factor better than O(log |X|). This
partly explains the dependence on α of the running time of our algorithms.

2

The Partitioning Scheme

Let Z be a point set with an associated metric d, let P ⊆ Z be a point set with at least
2 points, and n ≥ |P | be a parameter. For Q ⊆ Z, denote the maximum interpoint
distance (or diameter) of Q by diam(Q). Consider any partition of P into subsets (or blocks)
{P1 , P2 , . . . , Pt }, where 2 ≤ t ≤ |P |. Abusing notation, we will also view {P1 , P2 , . . . , Pt }
as a sequence of blocks. We say that Pi non-terminally (resp. terminally) intersects a ball
B if Pi intersects B and it is not (resp. it is) the last set in the sequence P1 , P2 , . . . , Pt
that intersects B. We would like to find a partition {P1 , P2 , . . . , Pt } of P that ensures the
following properties:
1. For each 1 ≤ i ≤ t, diam(Pi ) ≤ diam(P )/2.
)
2. For any ball B (centered at some point in Z) of radius r ≤ diam(P
16 log n , the expected size
r
of the set {i|Pi ∩ B 6= ∅} is at most 1 + c diam(P
) log n, where c > 0 is a constant. In
other words, the expected number of blocks in the partition that intersect B is at most
r
1 + c diam(P
) log n.
)
3. For any ball B (centered at some point in Z) of radius r ≤ diam(P
16 log n , the expected number
r
of blocks in the partition that non-terminally intersect B is at most c diam(P
) log n, where
c > 0 is a constant.

We note that the second property follows from the third, as the number of blocks that
intersect ball B is at most one more than the number of blocks that non-terminally intersect
B. We will design a probabilistic partitioning algorithm that finds a partition with the
desired properties.

2.0.1

The Partitioning Scheme of [13]

We first explain why the probabilistic partitioning algorithm of [13] does not achieve this
guarantee. In this algorithm, we first pick a β uniformly at random from the interval [ 8δ , 4δ ],
where δ = diam(P ). Also, let π1 , π2 , . . . , πp be a permutation of P chosen uniformly at
random. We compute P1 , P2 , . . . , Pp in order as follows. Suppose we already computed
P1 , . . . , Pi−1 . We let
Pi = {x ∈ P \ (P1 ∪ P2 ∪ · · · ∪ Pi−1 ) : d(x, πi ) ≤ β}.

S. Bandyapadhyay and K. Varadarajan

XX:5

We will refer to Pi as πi ’s cluster. We return the partition {Pi | Pi 6= ∅}.
Consider the following weighted tree. Let vertex u be connected to vertices u1 , u2 , . . . , ub
δ
using edges of weight 16 log
n . Here, n, δ, and b are parameters. Let V1 , V2 , . . . , Vb be disjoint
sets with b vertices each. For each i, ui is connected to every vertex in Vi using edges of
δ
weight 4δ − 16 log
n . Finally, z is a new vertex that is connected to u using an edge of weight
3δ
.
Consider
the
metric induced by this weighted graph, and let P denote the vertex set.
4
S
S
√
That is P = {u} ∪ i {ui } ∪ i Vi ∪ {z}. Set n := |P | and note that b = Θ( n). Also,
δ = diam(P ).
δ
Let B = B(u, r) where r = 16 log
n . Notice that the ball B consists of the points
{u, u1 , u2 , . . . , ub }. Consider running the probabilistic partitioning algorithm of [13], described
above, on P . We√argue that the expected number of blocks in the output partition that
r
intersect B is Ω( lognn ), which is asymptotically larger than 1 + c diam(P
) log n = O(1).
Fix 1 ≤ i ≤ b. We observe that in the output partition, ui belongs to the cluster of some
point in {u, u1 , u2 , . . . , ub } or of some point in Vi . Call ui isolated if ui belongs to the cluster
of some point in Vi . If ui is isolated, the cluster containing ui does not contain any of the
other uj . Thus, the number of blocks of the output partition that intersect B is at least the
number of vertices in {u1 , u2 , . . . , ub }that are isolated.
δ
δ
Note that ui is isolated if the following two events occur: (a) β ∈ [ 4δ − 16 log
n , 4 ]; (b)
some vertex in Vi appears in the random permutation π1 , π2 , . . . , πp before all vertices in
{u, u1 , . . . , ub }. The probability of these two events occuring is Ω( log1 n ). It follows that the
expected number of isolated vertices,
√ and thus the expected number of blocks in the partition
that intersect B, is Ω( logb n ) = Ω( lognn ).

2.0.2

Probability Distribution

Before describing our partitioning algorithm, we consider a probability distribution that it
uses. Given a positive real δ and an integer k ≥ 2, the distribution is denoted by dist(δ, k).
The probability density function (pdf) f of dist(δ, k) is the following:

f (x) =



 0



8 log k
δ
8 log k
δ

if x < δ/8 and x > δ/4
δ
if 8δ + (i − 1) 8 log
k ≤x<
δ
δ
if 4 − 8 log k ≤ x ≤ 4δ

1
2i
2
k

δ
8

δ
+ i 8 log
k for 1 ≤ i ≤ log k − 1

The following observation shows that f is indeed a density function.
I Observation 2.1. f is a probability density function.
Proof. It is sufficient to show that f satisfies the two properties of density function. As δ
and k are nonnegative it is easy to see that f (x) ≥ 0 for x ∈ (−∞, +∞). Also,
Z

∞

δ
δ
8 + 8 log k

Z
f (x)dx =
δ
8

−∞

Z

8 log k 1
dx +
δ 2

(log k−1)δ
δ
8+
8 log k

+ ... +
(log k−2)δ
δ
8+
8 log k

=

Z

δ
2δ
8 + 8 log k

8 log k 1
dx
δ 22
Z δ4
1
8 log k
8 log k 2
dx
dx
+
δ
δ
δ 2log k−1
δ k
4 − 8 log k
δ
δ
8 + 8 log k

log k−2
1 X 1
2
1 log k−1 2
+
=
1
−
(
)
+ =1
2 i=0 2i
k
2
k

J

XX:6

Approximate Clustering via Metric Partitioning

Consider the interval [ 8δ , 4δ ]. Now divide the interval into log k subintervals of equal length.
δ
δ
δ
The ith interval for 1 ≤ i ≤ log k − 1 is defined as [ 8δ + (i − 1) 8 log
k , 8 + i 8 log k ). The last
δ
δ
th
interval is [ 4δ − 8 log
interval by Ij for 1 ≤ j ≤ log k.
k , 4 ]. Denote the j
To sample a β according dist(δ, k), we first pick one of these intervals from the distribution
that assigns a probability of 1/2j to Ij for 1 ≤ j ≤ log k − 1, and a probability of 2/k to
Ilog k . Having picked an interval Ij , we generate β uniformly at random from it.
Now we discuss a vital property of the distribution dist(δ, k) which we use in the analysis
of the partitioning algorithm. For an event E, let Pr[E] denotes the probability that E
occurs. Now consider the following random process. We sample a value p from dist(δ, k).
Let Ej denotes the event that p ∈ Ij . Then we have the following observation.
Plog k
I Observation 2.2. Pr[Ej ] = i=j+1 P r[Ei ] for 1 ≤ j ≤ log k − 1.
Proof. The proof follows from the definition of the pdf of dist(δ, k).
Z
Pr[Ej ] =

δ
δ
8 +j 8 log k
δ
δ
8 +(j−1) 8 log k

1
1
2
2j+1
2
1
2
8 log k 1
dx
=
=
−
(1
−
+
=
)+
j
j
j
j
δ 2
2
2
k k
2
k
k

1
) 2
1
1
2
1 (1 − 2log k−j−1
(1
−
)
+
=
+
1
j
log
k−j−1
j+1
2
2
k
2
k
2
1
1
1
1
2
= j+1 ( 0 + 1 + . . . + log k−j−2 ) +
2
2
2
2
k
1
1
2
= j+1 + . . . + log k−1 +
2
2
k
log
Xk
= Pr[Ej+1 ] + . . . + Pr[Elog k−1 ] + Pr[Elog k ] =
P r[Ei ]

=

i=j+1

J

2.0.3

Partitioning Algorithm

Now we move on to the partitioning algorithm, which we recall, is given Z, a metric d on Z,
P ⊆ Z, and a parameter n ≥ |P |. The procedure RAND-PARTITION(P ) described below
(as Algorithm 1) takes a point set P ⊆ Z as input and outputs a partition with at most
|P | subsets. Suppose that P = {p1 , . . . , p|P | }. The algorithm then generates P1 , P2 , . . . , P|P |
in order via the for loop. Suppose that P1 , P2 , . . . , Pi−1 have already been constructed,
and Q = P \ (P1 ∪ P2 ∪ · · · ∪ Pi−1 ). To construct Pi , the procedure samples a βi from
dist(diam(P ), n). The choice of βi is done independently of the choices of the other points.
Then Pi is set to {x ∈ Q | d(x, pi ) ≤ βi }. Note that this is done in the i’th iteration of the
for loop. (Note that pi might not be assigned to Pi , as it could already be assigned to some
other subset.)
We show that RAND-PARTITION(P ) satisfies the two guarantees mentioned before.
To see that the first guarantee, note that the β values are chosen from the distribution
dist(diam(P ), n) which ensures that βi ≤ diam(P )/4 for 1 ≤ i ≤ p. Now each point in a subset
Pi is at a distance at most βi from pi . Thus by triangle inequality diam(Pi ) ≤ diam(P )/2.
In the next lemma we will show that the second guarantee also holds. Before that we have a
definition.
We say that Pi non-terminally (resp. terminally) intersects B(y, r) if Pi intersects B(y, r)
and it is not (resp. it is) the last set in the sequence P1 , P2 , . . . , Pp that intersects B(y, r).

S. Bandyapadhyay and K. Varadarajan

XX:7

Algorithm 1 RAND-PARTITION(P )
Require: A subset P = {p1 , . . . , p|P | } ⊆ Z
Ensure: A partition of P
1: p ← |P |
2: Q ← P
3: for i = 1 to p do
4:
sample a βi from dist(diam(P ), n) corresponding to pi
5:
Pi ← {x ∈ Q|d(x, pi ) ≤ βi }
6:
Q ← Q \ Pi
7: return {Pi |Pi 6= ∅ and 1 ≤ i ≤ p}

I Lemma 1. (Partitioning Lemma) There is a constant c such that for any ball B(y, r) with
)
r ≤ diam(P
16 log n , the expected number of blocks in the output of RAND-PARTITION(P ) that
r
intersect B(y, r) is at most 1 + c diam(P
) log n. Moreover, the expected number of blocks that
r
intersect the ball non-terminally is at most c diam(P
) log n.
The intuition for the lemma is as follows. Consider the beginning of the i’th iteration of
the for loop and assume that ball B(y, r) is not fully contained in the union of the previously
constructed blocks P1 , . . . , Pi−1 . Then, considering the choice of βi , the probability that
B(pi , βi ) fully contains the ball B(y, r) is nearly as large as the probability that B(pi , βi )
intersects B(y, r). If B(pi , βi ) fully contains the ball B(y, r), then of course none of the
blocks Pi+1 , Pi+2 , . . . , Pp intersect B(y, r). We now proceed to the proof.
Proof. For a point x ∈ Z and subset Q ⊆ Z, let dmin (x, Q) = minq∈Q d(x, q) and dmax (x, Q) =
)
maxq∈Q d(x, q). Fix the ball B(y, r) with r ≤ diam(P
16 log n . For each 1 ≤ i ≤ p, consider the
indicator random variable Ti defined as follows:

1 if Pi intersects B(y, r)
Ti =
0 otherwise
Pp
Let the random variable T = i=1 Ti be the number of subsets that the ball intersects.
Pp
Pp
Then E[T ] = i=1 E[Ti ] = i=1 P r[Pi intersects B(y, r)].
Clearly, there is at most one Pi that is the last one that intersects B(y, r). Thus,
p
X
i=1

P r[Pi intersects B(y, r)] ≤ 1 +

p
X

P r[Pi non-terminally intersects B(y, r)].

i=1

Let xi = dmin (pi , B(y, r)) and yi = dmax (pi , B(y, r)). By the triangle inequality, yi − xi ≤
2r. Denote by (S i ) the event that βi lands in the interval [xi , yi ]. Note that for Pi to nonterminally intersect B(y, r), the event (S i ) must occur. Thus, if the interval [xi , yi ] does not
) diam(P )
intersect the interval [ diam(P
,
], then P r[Pi non-terminally intersects B(y, r)] = 0.
8
4
) diam(P )
We therefore turn to the case where [xi , yi ] does intersect the interval [ diam(P
,
].
8
4
Recall that in defining the probability distribution dist(diam(P ), n), we have divided the
latter interval into log n subintervals I1 , I2 , . . . , Ilog n of equal length. Denote by al the
probability
P r[ a random sample drawn from dist(diam(P ), n) belongs to Il ].
For convenience, define Ilog n+1 = [diam(P )/4, ∞) and alog n+1 = 0.

XX:8

Approximate Clustering via Metric Partitioning
)
Let Ili be the subinterval that contains xi . (In case xi < diam(P
, let li = 1.) The length
8
of [xi , yi ] is at most 2r, 2r ≤ diam(P )/8 log n, and the length of each of the subintervals
is diam(P )/8 log n. Thus [xi , yi ] can intersect at most one more subinterval, and this is
Ili +1 . Let r1 and r2 be the length of Ili ∩ [xi , yi ] and Ili +1 ∩ [xi , yi ] respectively. Note that
r1 + r2 ≤ yi − xi ≤ 2r.
To bound P r[Pi non-terminally intersects B(y, r)], we now have two cases. We say that pi
is far (from the ball B(y, r)) if li ∈ {log n−1, log n}. We say that pi is near if 1 ≤ li ≤ log n−2.

Case 1: pi is far. In this case ali , ali +1 ≤
P r[S i ] ≤
≤
≤
=

2
n.

Thus

P r[βi lands in Ili ∩ [xi , yi ]] + P r[βi lands in Ili +1 ∩ [xi , yi ]]
r1
r2
al +
al +1
diam(P )/8 log n i diam(P )/8 log n i
2r
2
·
diam(P )/8 log n n
32r log n
.
n · diam(P )

Thus, P r[Pi non-terminally intersects B(y, r)] ≤ P r[S i ] ≤

32r log n
n·diam(P ) .

Case 2: pi is near. For such a pi we have the following crucial observation.
I Claim 2.1. P r[Pi non-terminally intersects B(y, r)] ≤

32r log n
diam(P ) P r[Pi

terminally intersects B(y, r)].

Proof. Suppose that P1 , P2 , . . . , Pi−1 have been chosen and B(y, r) ⊆ P1 ∪ P2 ∪ · · · ∪
Pi−1 . Conditioned on such a history, we have P r[Pi non-terminally intersects B(y, r)] =
P r[Pi terminally intersects B(y, r)] = 0 and the claimed inequality holds.
Now suppose that B(y, r) \ (P1 ∪ P2 ∪ · · · ∪ Pi−1 ) 6= ∅. Let us condition on such a history.
Then, Pi terminally intersects B(y, r) if βi lands in Ili +2 ∪ Ili +3 ∪ · · · ∪ Ilog n . Thus, using
Observation 2.2,

P r[Pi terminally intersects B(y, r)] ≥ ali +2 + ali +3 + · · · + alog n = ali +1 .
On the other hand,
P r[Pi non-terminally intersects B(y, r)] ≤
≤
≤
≤

P r[S i | βi ∈ Ili ∪ Ili +1 ] · P r[βi ∈ Ili ∪ Ili +1 ]


2
r1
1
r2
+
· (ali + ali +1 )
3 diam(P )/8 log n 3 diam(P )/8 log n
32 · r log n
· 3ali +1
3 · diam(P )
32 · r log n
· P r[Pi terminally intersects B(y, r)].
diam(P )
J

S. Bandyapadhyay and K. Varadarajan

XX:9

Hence the expected number of subsets that intersect B(y, r) non-terminally is
≤

p
X

P r[Pi non-terminally intersects B(y, r)]

i=1

≤

X

P r[Pi non-terminally intersects B(y, r)]

i:pi is far

X

+

P r[Pi non-terminally intersects B(y, r)]

i:pi is near
p
X

p

32r log n
1
32r log n X
+
P r[Pi terminally intersects B(y, r)]
diam(P ) i=1 n diam(P ) i=1
r
≤ c
log n.
diam(P )
Pp
For the last inequality, we used the fact that i=1 P r[Pi terminally intersects B(y, r)] = 1,
since there is exactly one Pi that terminally intersects B(y, r). Putting the two cases together,
we have
≤

E[T ] ≤ 1 + c

r
log n.
diam(P )
J

We conclude by summarizing the result.
I Theorem 2. Let Z be a point set with an associated metric d, let P ⊆ Z be a point set
with at least 2 points, and n ≥ |P | be a parameter. There is a polynomial-time probabilistic
algorithm RAND-PARTITION(P ) that partitions P into blocks {P1 , P2 , . . . , Pt } and has the
following guarantees:
1. For each 1 ≤ i ≤ t, diam(Pi ) ≤ diam(P )/2.
2. There is a constant c > 0 so that for any ball B (centered at some point in Z) of radius
)
r
r ≤ diam(P
16 log n , the expected size of the set {i|Pi ∩ B 6= ∅} is at most 1 + c diam(P ) log n and
r
the expected number of blocks that non-terminally intersect B is at most c diam(P
) log n.

3

Algorithm for MCC

We now describe our (1 + )-factor approximation algorithm for the MCC problem. Recall
that we are given a set X of clients, a set Y of servers, and a metric d on X ∪ Y . We wish to
compute a cover for X with minimum cost. Let m = |Y | and n = |X|.
For P ⊆ X, let opt(P ) denote some optimal cover for P . Denote by cost(B) the cost of a
P
ball B (the α-th power of B’s radius) and by cost(B) the cost B∈B cost(B) of a set B of
balls.
To compute a cover for P , our algorithm first guesses the set Q ⊆ opt(P ) consisting of
all the large balls in opt(P ). As we note in the structure lemma below, we may assume that
the number of large balls in opt(P ) is small. We then use the algorithm of Theorem 2 to
partition P into {P1 , P2 , . . . , Pt }. For each 1 ≤ i ≤ t, we recursively compute a cover for the
set Pi0 ⊆ Pi of points not covered by Q.
To obtain an approximation guarantee for this algorithm, we use the guarantees of
Theorem 2. With this overview, we proceed to the structure lemma and a complete description
of the algorithm.

XX:10

Approximate Clustering via Metric Partitioning

3.1

A Structure Lemma

It is not hard to show that for any γ ≥ 1 and P ⊆ X such that diam(P ) is at least a constant
factor of diam(X ∪ Y ), opt(P ) contains at most (c/γ)α balls of radius at least diam(P )/γ.
Here c is some absolute constant. The following structural lemma extends this fact.
I Lemma 3. Let P ⊆ X, 0 < λ < 1 and γ ≥ 1, and suppose that opt(P ) does not contain
any ball of radius greater than or equal to 2α · diam(P )/λ. Then the number of balls in
opt(P ) of radius greater than or equal to diam(P )/γ is at most c(λ, γ) := (9αγ/λ)α .
Proof. Suppose that opt(P ) does not contain any ball of radius greater than or equal
to 2α · diam(P )/λ. Note that each ball in opt(P ) intersects P and has radius at most
2α · diam(P )/λ. Thus the point set {z ∈ X ∪ Y | z ∈ B for some B ∈ opt(P )} has diameter
at most diam(P ) + 8α · diam(P )/λ ≤ 9α · diam(P )/λ. It follows that there is a ball centered
at a point in Y , with radius at most 9α · diam(P )/λ that contains P .
Let t denote the number of balls in opt(P ) of radius greater than or equal to diam(P )/γ.
By optimality of opt(P ), we have t · (diam(P )/γ)α ≤ (9α · diam(P )/λ)α . Thus t ≤ (9αγ/λ)α .
J

3.2

The Algorithm

We may assume that the minimum distance between two points in X is 1. Let L =
1 + log(diam(X)). As we want a (1 + ε)-approximation, we fix a parameter λ = ε/2L. Let
n
γ = c log
λ , where c is the constant in Theorem 2. Denote D to be the set of balls such that
each ball is centered at a point of y ∈ Y and has radius r = d(x, y) for some x ∈ X. We note
that for any P ⊆ X, any ball in opt(P ) must belong to this set. Note that |D| ≤ mn. Recall
that c(λ, γ) = (9αγ/λ)α .
With this terminology, the procedure POINT-COVER(P ) described as Algorithm 2
returns a cover of P ⊆ X. If |P | is smaller than some constant, then the procedure returns an
optimal solution by searching all covers with a constant number of balls. In the general case,
one candidate solution is the best single ball solution. For the other candidate solutions, the
procedure first computes a partition {P1 , . . . , Pτ } of P , using the RAND-PARTITION(P )
procedure. Here RAND-PARTITION(P ) is called with Z = X ∪ Y and n = |X| ≥ |P |. Then
it iterates over all possible subsets of D of size at most c(λ, γ) containing balls of radius
greater than diam(P )/γ. For each such subset Q and 1 ≤ i ≤ τ , it computes the set Pi0 ⊆ Pi
of points not covered by Q. It then makes recursive calls and generates the candidate solution
Sτ
Q ∪ i=1 POINT-COVER(Pi0 ). Note that all the candidate solutions are actually valid covers
for P . Among these candidate solutions the algorithm returns the best solution.
Our overall algorithm for MCC calls the procedure POINT-COVER(X) to get a cover of
X.

3.3

Approximation Guarantee

For P ⊆ X, let level(P ) denote the smallest non-negative integer i such that diam(P ) < 2i .
As the minimum interpoint distance in X is 1, level(P ) = 0 if and only if |P | ≤ 1. Note that
level(X) ≤ L.
The following lemma bounds the quality of the approximation of our algorithm.
I Lemma 4. POINT-COVER(P ) returns a solution whose expected cost is at most (1 +
λ)l cost(opt(P )), where l = level(P ).

S. Bandyapadhyay and K. Varadarajan

XX:11

Algorithm 2 POINT-COVER(P )
Require: A subset P ⊆ X.
Ensure: A cover of the points in P .
1: if |P | is smaller than some constant κ then
2:
return a minimum solution by checking all covers with at most κ balls.
3: sol ← the best cover with one ball
4: cost ← cost(sol)
5: Let {P1 , . . . , Pτ } be the set of nonempty subsets returned by RAND-PARTITION(P )
diam(P )
6: Let B be the set of balls in D having radius greater than
γ
7: for each Q ⊆ B of size at most c(λ, γ) do
8:
for i = 1 to τ do
S
9:
Let Pi0 = {p ∈ Pi | p 6∈ B∈Q B}
S
τ
10:
Q0 ← Q ∪ i=1 POINT-COVER(Pi0 )
11:
if cost(Q0 ) < cost then
12:
cost ← cost(Q0 )
13:
sol ← Q0
14: return sol

Proof. We prove this lemma using induction on l. If l = 0, then |P | ≤ 1 and POINTCOVER(P ) returns an optimal solution, whose cost is cost(opt(P )). Thus assume that l ≥ 1
and the statement is true for subsets having level at most l −1. Let P ⊆ X be a point set with
level(P ) = l. If |P | is smaller than the constant threshold κ, POINT-COVER(P ) returns an
optimal solution. So we may assume that |P | is larger than this threshold. We have two cases.
Case 1: There is some ball in opt(P ) whose radius is at least 2α · diam(P )/λ. Let B denote
such a ball and r(B) ≥ 2α · diam(P )/λ be its radius. Since (1 + λ/2α)r(B) ≥ r(B) + diam(P ),
the concentric ball of radius (1 + λ/2α)r(B) contains P . It follows that there is a cover for
P that consists of a single ball and has cost at most
(1 + λ/2α)α r(B)α ≤ (1 + λ)cost(opt(P )) ≤ (1 + λ)l cost(opt(P )).
Case 2: There is no ball in opt(P ) whose radius is at least 2α · diam(P )/λ. Let Q0 ⊆ opt(P )
contain those balls of radius at least diam(P )/γ. It follows from Lemma 3 that |Q0 | ≤ c(λ, γ).
Thus the algorithm considers a Q with Q = Q0 . Fix this iteration. Also fix the partition
{P1 , . . . , Pτ } of P computed by RAND-PARTITION(P ). RAND-PARTITION ensures that
diam(Pi ) ≤ diam(P )/2 for 1 ≤ i ≤ τ . Thus diam(Pi0 ) ≤ diam(P )/2 and the level of each Pi0
is at most l − 1. Hence by induction the expected value of cost(POINT-COVER(Pi0 )) is at
most (1 + λ)l−1 cost(opt(Pi0 )).
τ
P
Let S 0 = opt(P ) \ Q0 . We argue below that the expected value of
cost(opt(Pi0 )) is at
most (1 + λ)cost(S 0 ). Assuming this, we have

E[cost(Q0 ∪

τ
[

i=1

POINT-COVER(Pi0 ))] ≤ cost(Q0 ) + (1 + λ)l−1 E[

i=1

τ
X
i=1

≤ cost(Q0 ) + (1 + λ)l cost(S 0 )
≤ (1 + λ)l cost(opt(P )).

cost(opt(Pi0 ))]

XX:12

Approximate Clustering via Metric Partitioning

Thus POINT-COVER(P ) returns a solution whose expected cost is at most (1+λ)l cost(opt(P )),
as desired.
Pτ
We now argue that the expected value of i=1 cost(opt(Pi0 )) is at most (1 + λ)cost(S 0 ).
Let Bi consist of those balls in S 0 that intersect Pi . For B ∈ S 0 , let µ(B) denote the number
of blocks in the partition {P1 , . . . , Pτ } that B intersects. Because Bi is a cover for Pi0 , we
have cost(opt(Pi0 )) ≤ cost(Bi ). Thus
τ
X

cost(opt(Pi0 )) ≤

i=1

τ
X

cost(Bi ) =

X

µ(B)cost(B).

B∈S 0

i=1

By definition of Q0 , any ball B ∈ S 0 = opt(P )\Q0 has radius at most

diam(P )
γ

where c is the constant in Theorem 2. We may assume that c ≥ 16 and hence
diam(P )
16 log n .

λ·diam(P )
c log n ,
λ·diam(P )
≤
c log n

=

Theorem 2 now implies that

c · r(B) log n
c log n λ · diam(P )
≤1+
·
= 1 + λ.
diam(P )
diam(P )
c log n
Pτ
Thus the expected value of i=1 cost(opt(Pi0 )) is at most
X
X
E[µ(B)]cost(B) ≤ (1 + λ)
cost(B) = (1 + λ)cost(S 0 ),
E[µ(B)] ≤ 1 +

B∈S 0

B∈S 0

J

as claimed.

We conclude that the expected cost of the cover returned by POINT-COVER(X) is at
most (1 + λ)L cost(opt(X)) ≤ (1 + ε)cost(opt(X)), since λ = ε/2L.
Now consider the time complexity of the algorithm. POINT-COVER(P ) makes (mn)O(c(λ,γ))
direct recursive calls on subsets of diameter at most diam(P )/2. Thus the overall time complexity of POINT-COVER(X) can be bounded by (mn)O(c(λ,γ)L) . Plugging in λ = ε/2L,
γ = c log n/λ, and c(λ, γ) = (9αγ/λ)α , we conclude
αL2 logn α

I Theorem 5. There is an algorithm for MCC that runs in time (mn)O( 2 ) L and
returns a cover whose expected cost is at most (1 + ε) times the optimal. Here L is 1 plus the
logarithm of the aspect ratio of X, that is, the ratio of the maximum and minimum interpoint
distances in the client set X.
Using relatively standard techniques, which we omit here, we can pre-process the input
to ensure that the ratio of the maximum and minimum interpoint distances in X is upper
bounded by a polynomial in mn
ε . However, this affects the optimal solution by a factor of
at most (1 + ). After this pre-processing, we have L = O(log mn
ε ). Using the algorithm
in Theorem 5 after the pre-processing, we obtain a (1 + ) approximation with the quasiO(1)
mn
polynomial running time O(2log
). Here the O(1) hides a constant that depends on α
and ε.

4

Algorithm for k-clustering

Recall that in k-clustering we are given a set X of points, a metric d on X, and a positive
integer k. Let |X| = n. For P ⊆ X and integer κ ≥ 0, let opt(P, κ) denote an optimal
solution of κ-clustering for P (using balls whose center can be any point in X). We reuse the
notions of level(P ), cost(B) and cost(B) from Section 3, for a point set P , a ball B, and a
set B of balls, respectively. Denote D to be the set of balls such that each ball is centered at

S. Bandyapadhyay and K. Varadarajan

a point of y ∈ X and has radius r = d(x, y) for some x ∈ X. We note that for any P ⊆ X,
any ball in opt(P, κ) must belong to this set. Note that |D| ≤ n2 .
To start with we prove a structure lemma for k-clustering.
I Lemma 6. Let P ⊆ X, κ be a positive integer, and γ ≥ 1. Then the number of balls in
opt(P, κ) of radius greater than or equal to diam(P )/γ is at most c(γ) := γ α .
Proof. Note that any ball centered at a point in P and having radius diam(P ) contains all
the points of P . Now by definition of diam(P ) and D, there is a point x ∈ P such that the
ball B(x, diam(P )) ∈ D. Hence opt(P, κ) ≤ diam(P )α .
Let t denote the number of balls in opt(P, κ) of radius greater than or equal to diam(P )/γ.
By optimality of opt(P, κ), we have t · (diam(P )/γ)α ≤ diam(P )α . Thus t ≤ γ α .
J
Like in the case of MCC, we assume that the minimum distance between two points in
n
X is 1. Let L = 1 + log(diam(X)). We fix a parameter λ = ε/6L. Let γ = c log
λ , where c is
the constant in Theorem 2.
We design a procedure CLUSTERING(P, κ) (see Algorithm 3) that given a subset P
of X and an integer κ, returns a set of at most (1 + 3λ)l κ balls whose union contains P ,
where l = level(P ). We overview this procedure, focussing on the differences from the
procedure POINT-COVER() used to solve the MCC problem. In CLUSTERING(P, κ),
RAND-PARTITION(P ) is called with Z = X and n = |X| ≥ |P |. We require two properties
of the partition {P1 , . . . , Pτ } of P computed by RAND-PARTITION(P ). Let Q0 be the
set containing the large balls of opt(P, κ), that is, those with radius at least diam(P )/γ.
Let S 0 = opt(P, κ) \ Q0 denote the set of small balls, and let S 0 i ⊆ S 0 consist of those
balls that contain at least one point in Pi that is not covered by Q0 . We would like (a)
Pτ
Pτ
0
0
0
0
i=1 cost(S i ) ≤ (1 + 3λ)cost(S ), and (b)
i=1 |S i | ≤ (1 + 3λ)|S |. Theorem 2 ensures
that each of (a) and (b) holds in expectation. However, we would like both (a) and (b) to
hold simultaneously, not just in expectation. For this reason, we try Θ(log n) independent
random partitions in Line 6, ensuring that with high probability, properties (a) and (b) hold
for at least one of them.
Now let us fix one of these Θ(log n) trials where we got a partition {P1 , . . . , Pτ } satisfying
properties (a) and (b), and also fix an iteration in Line 9 where we have Q = Q0 . Let
Pi0 ⊆ Pi be the points not covered by Q0 . For each 1 ≤ i ≤ τ and 0 ≤ κ1 ≤ (1 + 3λ)κ, we set
cluster(Pi0 , κ1 ) to be the cover obtained by recursively invoking CLUSTERING(Pi0 , κ1 ) (as
in Line 13).
Let us call a tuple (κ1 , κ2 , . . . , κτ ) of integers valid if 0 ≤ κi ≤ (1 + 3λ)(κ − |Q0 |) and
Pτ
Pτ
0
i=1 κi ≤ (1 + 3λ)(κ − |Q0 |). We would like to minimize
i=1 cost(cluster(Pi , κi )) over all
valid tuples (κ1 , κ2 , . . . , κτ ). As there are too many valid tuples to allow explicit enumeration,
we solve this optimization problem in Lines 14–21 via a dynamic programming approach.
This completes our overview. Our overall algorithm for k-clustering calls the procedure
CLUSTERING(X, k). Next we give the approximation bound on the cost of the solution
returned by CLUSTERING(P, κ).
I Lemma 7. For any P ⊆ X and an integer κ ≥ 1, CLUSTERING(P, κ) returns a solution
consisting of at most (1 + 3λ)l κ balls and with probability at least 1 − |Pn|−1
, the cost of the
2
l
solution is at most (1 + 3λ) cost(opt(P, κ)), where l = level(P ).
Proof. We prove this lemma using induction on l. If l = 0, then |P | ≤ 1 and CLUSTERING(P,
κ) returns an optimal solution, whose cost is cost(opt(P, κ)). Thus assume that l ≥ 1 and
the statement is true for subsets having level at most l − 1. If |P | is smaller than the constant

XX:13

XX:14

Approximate Clustering via Metric Partitioning

Algorithm 3 CLUSTERING(P, κ)
Require: A subset P ⊆ X, an integer κ.
Ensure: A set of balls whose union contains the points in P .
1: if |P | is smaller than some constant β then
2:
return a minimum solution by checking all solutions with at most min{κ, β} balls.
3: sol ← the best solution with one ball
4: cost ← cost(sol)
5: l ← level(P )
6: for all 2 log3/2 n iterations do
Let {P1 , . . . , Pτ } be the set of nonempty subsets returned by RAND-PARTITION(P )
7:
)
8:
Let B be the set of balls in D having radius greater than diam(P
γ
9:
for each Q ⊆ B of size at most c(γ) do
10:
for i = 1 to τ do
S
11:
Let Pi0 = {p ∈ Pi | p 6∈ B∈Q B}
12:
for each 1 ≤ i ≤ τ and 0 ≤ κ1 ≤ (1+3λ)κ do
13:
cluster(Pi0 , κ1 ) ← CLUSTERING(Pi0 , κ1 )
14:
for i = 0 to τ − 1 do
Sτ
15:
Ri ← j=i+1 Pj0
16:
for κ1 = 0 to (1+3λ)κ do
17:
cluster(Rτ −1 , κ1 ) ← cluster(Pτ0 , κ1 )
18:
for all i = τ − 2 to 0 and 0 ≤ κ1 ≤ (1+3λ)κ do
0
19:
κ0min ← arg minκ0 :0≤κ0 ≤κ1 cost(cluster(Pi+1
, κ0 ) ∪ cluster(Ri+1 , κ1 − κ0 ))
0
0
20:
cluster(Ri , κ1 ) ← cluster(Pi+1 , κmin ) ∪ cluster(Ri+1 , κ1 − κ0min )
0
21:
Q ← Q ∪ cluster(R0 , (1 + 3λ) · (κ − |Q|))
22:
if |Q0 | ≤ (1+3λ)l κ and cost(Q0 ) < cost then
23:
cost ← cost(Q0 )
24:
sol ← Q0
25: return sol

threshold β, CLUSTERING(P, κ) returns an optimal solution. So we may assume that |P |
is larger than this threshold.
Consider one of the 2 log3/2 n iterations of CLUSTERING(P, κ). Fix the partition
{P1 , . . . , Pτ } of P computed by RAND-PARTITION(P ) in this iteration. Let Q0 be the set
containing the balls of opt(P, κ) with radius at least diam(P )/γ. It follows from Lemma 6
that |Q0 | ≤ c(γ). Fix the choice Q = Q0 .
RAND-PARTITION(P ) ensures that diam(Pi ) ≤ diam(P )/2 for 1 ≤ i ≤ τ . Thus
diam(Pi0 ) ≤ diam(P )/2 and the level of each Pi0 is at most l − 1. Hence by induction,
|P 0 |−1
cluster(Pi0 , κ1 ) contains at most (1+3λ)l−1 κ1 balls and with probability at least 1 − in2 ,
its cost is at most (1 + 3λ)l−1 cost(opt(Pi0 , κ1 )) for 1 ≤ κ1 ≤ (1 + 3λ)κ.
Let S 0 = opt(P, κ) \ Q0 . Thus |S 0 | ≤ κ − |Q0 |. We note that the union of the balls in S 0
contains the points in ∪τi=1 Pi0 . Let S 0 i ⊆ S 0 be the set of balls that intersect with Pi0 and
thus the union of balls in S 0 i contains Pi0 , where 1 ≤ i ≤ τ . We argue below that the value
Pτ
Pτ
of i=1 |S 0 i | is at most (1 + 3λ)|S 0 | and the value of i=1 cost(opt(Pi0 , |S 0 i |)) is at most
(1 + 3λ)cost(S 0 ) with probability at least 1/3. Then the probability is at least 1 − n12 that
Pτ
corresponding to one of the 2log3/2 n iterations the value of i=1 |S 0 i | is at most (1 + 3λ)|S 0 |
Pτ
and the value of i=1 cost(opt(Pi0 , |S 0 i |)) is at most (1 + 3λ)cost(S 0 ). We refer to this event
as the first good event. Now let us assume that the first good event occurs.

S. Bandyapadhyay and K. Varadarajan

XX:15

Note that by induction, cluster(Pi0 , |S 0 i |) contains at most (1 + 3λ)l−1 |S 0 i | balls and
|P 0 |−1
with probability at least 1 − in2 , its cost is at most (1 + 3λ)l−1 cost(opt(Pi0 , |S 0 i |)) for
1 ≤ i ≤ τ . The probability that for every 1 ≤ i ≤ τ , the cost of cluster(Pi0 , |S 0 i |) is at most
(1 + 3λ)l−1 cost(opt(Pi0 , |S 0 i |)) and it contains at most (1 + 3λ)l−1 |S 0 i | balls, is at least
τ
Y

τ

1−

i=1

|Pi0 | − 1 Y
|P | − 2
|Pi | − 1
≥
≥1−
.
1−
2
2
n
n
n2
i=1

We refer to this event as the second good event. Assuming this second good event occurs,
Sτ
Pτ
it follows by an easy induction on i that cluster(Ri , j=i+1 |S 0 j |) covers Ri = j=i+1 Pj0 with at
P
P
τ
τ
most (1+3λ)l−1 j=i+1 |S 0 j | balls and its cost is at most (1+3λ)l−1 j=i+1 cost(opt(Pj0 , |S 0 j |)).
Pτ
Sτ
Pτ
Thus cluster(R0 , i=1 |S 0 i |) covers R0 = i=1 Pi0 with at most (1 + 3λ)l−1 i=1 |S 0 i | balls
P
Pτ
τ
and its cost is at most (1+3λ)l−1 i=1 cost(opt(Pi0 , |S 0 i |)). Hence Q0 ∪ cluster(R0 , i=1 |S 0 i |)
covers P . Now assuming both the good events occur, we have
|Q0 ∪ cluster(R0 ,

τ
X

|S 0 i |)|

≤

|Q0 | +

τ
X

(1+3λ)l−1 |S 0 i |

i=1

i=1

τ
X

|S 0 i |

≤

|Q0 | + (1+3λ)l−1

≤

|Q0 | + (1+3λ)l |S 0 |

≤

|Q0 | + (1+3λ)l (κ − |Q0 |)

i=1

≤ (1+3λ)l κ.
cost(Q0 ∪ cluster(R0 ,

τ
X

|S 0 i |))

≤ cost(Q0 ) + (1+3λ)l−1

τ
X

cost(opt(Pi0 , |S 0 i |))

i=1

i=1

≤

cost(Q0 ) + (1+3λ) cost(S 0 )

≤

(1+3λ)l cost(opt(P, κ)).

l

The probability that both the good events occur is at least
(1 −

|P | − 2
1
|P | − 1
) · (1 − 2 ) ≥ 1 −
.
2
n
n
n2

Pτ
0
Hence the statement of the lemma follows by noting that the value of
i=1 |S i | in
Pτ
0
cluster(R0 , i=1 |S i |) is at most (1 + 3λ) · (κ − |Q0 |).
Pτ
We now argue that the probability that i=1 |S 0 i | is greater than (1 + 3λ)|S 0 | is at most
Pτ
1/3 and the probability that i=1 cost(opt(Pi0 , |S 0 i |)) is greater than (1 + 3λ)cost(S 0 ) is at
Pτ
most 1/3. Then using union bound, the probability that i=1 |S 0 i | is at most (1 + 3λ)|S 0 |
Pτ
and i=1 cost(opt(Pi0 , |S 0 i |)) is at most (1 + 3λ)cost(S 0 ) is at least 1/3.
For B ∈ S 0 , let µ(B) denote the number of blocks in the partition {P1 , . . . , Pτ } that
non-terminally intersect B. We note that at most one block can terminally intersect B.
Because S 0 i is a cover for Pi0 with |S 0 i | balls, we have cost(opt(Pi0 , |S 0 i |)) ≤ cost(S 0 i ). Thus
τ
X

cost(opt(Pi0 , |S 0 i |)) ≤

τ
X

cost(S 0 i ) =

i=1

i=1

X

(1+µ(B))cost(B) = cost(S 0 )+

B∈S 0

and,
τ
X
i=1

|S 0 i | ≤

X
B∈S 0

(1 + µ(B)) = |S 0 | +

X
B∈S 0

µ(B).

X

B∈S 0

µ(B)cost(B).

XX:16

Approximate Clustering via Metric Partitioning

By definition of Q0 , any ball B ∈ S 0 = opt(P, κ) \ Q0 has radius at most
λ·diam(P )
c log n , where c is the constant in Theorem 2.
λ·diam(P )
)
≤ diam(P
c log n
16 log n . Theorem 2 now implies that

E[µ(B)] ≤

diam(P )
γ

=

We may assume that c ≥ 16 and hence

c · r(B) log n
c log n λ · diam(P )
≤
·
= λ.
diam(P )
diam(P )
c log n

Using linearity of expectation,
X
X
E[
µ(B)] =
E[µ(B)] ≤ λ · |S 0 |.
B∈S 0

B∈S 0

Now by Markov’s inequality,
P r[

X

µ(B) > 3λ · |S 0 |] ≤ 1/3.

B∈S 0

It follows that,
P r[

τ
X

|S 0 i | > (1 + 3λ)|S 0 |]

i=1

≤

P r[|S 0 | +

X

µ(B) > (1 + 3λ)|S 0 |]

B∈S 0

≤

P r[

X

µ(B) > 3λ · |S 0 |] ≤ 1/3.

B∈S 0

Again using linearity of expectation,
X
X
E[
µ(B)cost(B)] =
E[µ(B)]cost(B) ≤ λ · cost(S 0 ).
B∈S 0

B∈S 0

Now by Markov’s inequality,
X
P r[
µ(B)cost(B) > 3λ · cost(S 0 )] ≤ 1/3.
B∈S 0

It follows that,
P r[

τ
X

cost(opt(Pi0 , |S 0 i |)) > (1 + 3λ)cost(S 0 )]

i=1

≤

P r[cost(S 0 ) +

X

µ(B)cost(B) > (1 + 3λ)cost(S 0 )]

B∈S 0

≤

P r[

X

µ(B)cost(B) > 3λ · cost(S 0 )] ≤ 1/3.

B∈S 0

J
Since λ = ε/6L, (1 + 3λ)L ≤ 1 + ε. Thus we conclude that with probability at least 1 − n1 ,
CLUSTERING(X, k) returns a solution with at most (1 + ε)k balls whose cost is at most
(1 + ε)cost(opt(X, k)).
Now consider the time complexity of the algorithm. CLUSTERING(P, κ) makes nO(c(γ))
direct recursive calls on subsets of diameter at most diam(P )/2. Thus the overall time
complexity of CLUSTERING(X, k) can be bounded by nO(c(γ)L) . Plugging in λ = ε/6L,
γ = c log n/λ, and c(γ) = γ α , we conclude

S. Bandyapadhyay and K. Varadarajan

XX:17

Llogn α

I Theorem 8. There is a randomized algorithm for k-clustering that runs in time nO((  ) L)
and with probability at least 1 − n1 returns a solution with at most (1 + ε)k balls whose cost
is at most (1 + ε) times the optimal. Here L is 1 plus the logarithm of the aspect ratio of X,
that is, the ratio of the maximum and minimum interpoint distances in the set X.

5

Inapproximability Result

In this section we present an inapproximability result which complements the result in
Section 3. In particular here we consider the case when α is not a constant. The heart of
this result is a reduction from the dominating set problem. Given a graph G = (V, E), a
dominating set for G is a subset V 0 of V such that for any vertex v ∈ V \ V 0 , v is connected
to at least one vertex of V 0 by an edge in E. The dominating set problem is defined as follows.
Dominating Set Problem (DSP)
INSTANCE: Graph G = (V, E), positive integer k ≤ |V |.
QUESTION: Is there a dominating set for G of size at most k?
The following inapproximability result is proved by Kann [20].
I Theorem 9. There is a constant c > 0 such that there is no polynomial-time c log |V |-factor
approximation algorithm for DSP assuming P =
6 N P.
The following theorem shows an inapproximability bound for MCC when α ≥ log |X|.
I Theorem 10. For α ≥ log |X|, no polynomial time algorithm for MCC can achieve an
approximation factor better than c log |X| assuming P =
6 N P.
Proof. To prove this theorem we show a reduction from DSP. Given an instance (G =
(V, E), k) of DSP we construct an instance of MCC. The instance of MCC consists of
two sets of points X (clients) and Y (servers), and a metric d defined on X ∪ Y . Let
V = {v1 , v2 , . . . , vn }, where n = |V |. For each vi ∈ V , Y contains a point yi and X contains
a point xi . For any point p ∈ X ∪ Y , d(p, p) = 0. For i, j ∈ [n], d(xi , yj ) is 1 if i = j or
the edge (vi , vj ) ∈ E, and d(xi , yj ) is 3 otherwise. For i, j ∈ [n] such that i 6= j, we set
d(xi , xj ) = d(yi , yj ) = 2.
Consider two nonadjacent vertices vi and vj . For any xt ∈ X such that t 6= i, j,
d(xi , xt ) + d(xt , yj ) ≥ 3. Similarly, for any yt ∈ Y such that t 6= i, j, d(xi , yt ) + d(yt , yj ) ≥ 3.
Thus d defines a metric. Next we will prove that G has a dominating set of size at most k iff
the cost of covering the points in X using the balls around the points in Y is at most k.
Suppose G has a dominating set J of size at most k. For each vertex vj ∈ J, build a
radius 1 ball around yj . We return this set of balls B as the solution of MCC. Now consider
any point xi ∈ X. If vi ∈ J, then xi is covered by the ball around yi . Otherwise, there must
be a vertex vj ∈ J such that (vi , vj ) ∈ E. Then d(xi , yj ) is 1 and xi is covered by the ball
around yj . Hence B is a valid solution of MCC with cost at most k.
Now suppose there is a solution B of MCC with cost at most k. If k > |X|, then V is a
dominating set for G of size |X| < k. If k ≤ |X|, our claim is that the radius of each ball in
B is 1. Suppose one of the balls B has a radius more than 1. Then the way the instance of
MCC is created the radius should be at least 3. Hence k ≥ 3α ≥ 3log |X| > |X|, which is a
contradiction. Now consider the set of vertices J corresponding to the centers of balls in B.
It is not hard to see that J is a dominating set for G of size at most k.
Let OPT be the cost of any optimal solution of MCC for the instance (X, Y, d). Then by
the properties of this reduction the size of any minimum dominating set for G is OPT. Thus if

XX:18

REFERENCES

there is an approximation algorithm for MCC that gives a solution with cost (c log |X|)·OPT,
then using the reduction we can produce a dominating set of size (c log |V |)·OPT. Then from
Theorem 9 it follows that P = N P. This completes the proof of our theorem.
J

6

Conclusions

One generalization of the MCC problem that has been studied [9, 8] includes fixed costs for
opening the servers. As input, we are given two point sets X (clients) and Y (servers), a
metric on Z = X ∪ Y , and a facility cost fy ≥ 0 for each server y ∈ Y . The goal is to find a
subset Y 0 ⊆ Y , and a set of balls {By |y ∈ Y 0 and By is centered at y} that covers X, so as
P
to minimize y∈Y 0 (fy + r(By )α ). It is not hard to see that our approach generalizes in a
straightforward way to give a (1 + ε) approximation to this problem using quasi-polynomial
running time. To keep the exposition clear, we have focussed on the MCC rather than this
generalization.
The main open problem that emerges from our work is whether there one can obtain a
(1 + ε)-approximation for the k-clustering problem in quasi-polynomial time.
Acknowledgements. We would like to thank an anonymous reviewer of an earlier version of
this paper for suggestions that improved the guarantees and simplified the proof of Theorem 2.
We also thank other reviewers for their feedback and pointers to the literature.

References
1 Ittai Abraham, Yair Bartal, and Ofer Neimany. Advances in metric embedding theory. In
Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages
271–286. ACM, 2006.
2 Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete,
Christian Knauer, Jonathan Lenchner, Joseph S. B. Mitchell, and Kim Whittlesey.
Minimum-cost coverage of point sets by disks. In Proceedings of the 22nd ACM Symposium
on Computational Geometry, Sedona, Arizona, USA, June 5-7, 2006, pages 449–458,
2006.
3 Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for
euclidean k-medians and related problems. In Proceedings of the Thirtieth Annual ACM
Symposium on Theory of Computing, STOC ’98, pages 106–113, New York, NY, USA,
1998. ACM.
4 Sayan Bandyapadhyay and Kasturi R. Varadarajan. On variants of k-means clustering.
In 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18,
2016, Boston, MA, USA, pages 14:1–14:15, 2016.
5 Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications.
In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington,
Vermont, USA, 14-16 October, 1996, pages 184–193. IEEE Computer Society, 1996.
6 Yair Bartal. Graph decomposition lemmas and their role in metric embedding methods.
In Algorithms–ESA 2004, pages 89–97. Springer, 2004.
7 Babak Behsaz and Mohammad R. Salavatipour. On minimum sum of radii and diameters
clustering. In Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and
Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings, pages 71–82, 2012.
8 Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos.
Geometric clustering to minimize the sum of cluster sizes. In Algorithms - ESA 2005, 13th

REFERENCES

9
10

11

12
13
14

15
16
17
18
19

20

21
22
23

Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings,
pages 460–471, 2005.
Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters.
J. Comput. Syst. Sci., 68(2):417–441, 2004.
Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics. In FOCS,
to appear, 2016.
Srinivas Doddi, Madhav V. Marathe, S. S. Ravi, David Scot Taylor, and Peter Widmayer.
Approximation algorithms for clustering to minimize the sum of diameters. Nord. J.
Comput., 7(3):185–203, 2000.
Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes
for geometric intersection graphs. SIAM J. Comput., 34(6):1302–1323, 2005.
Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating
arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485–497, 2004.
Ari Freund and Dror Rawitz. Combinatorial interpretations of dual fitting and primal
fitting. In Approximation and Online Algorithms, First International Workshop, WAOA
2003, Budapest, Hungary, September 16-18, 2003, Revised Papers, pages 137–150, 2003.
Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan.
On metric clustering to minimize the sum of radii. Algorithmica, 57(3):484–498, 2010.
Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan.
On clustering to minimize the sum of radii. SIAM J. Comput., 41(1):47–60, 2012.
Sariel Har-Peled. Geometric approximation algorithms, 2011.
Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and
packing problems in image processing and VLSI. J. ACM, 32(1):130–136, 1985.
Lior Kamma, Robert Krauthgamer, and Huy L Nguyên. Cutting corners cheaply, or
how to remove steiner points. In Proceedings of the Twenty-Fifth Annual ACM-SIAM
Symposium on Discrete Algorithms, pages 1029–1040. SIAM, 2014.
Viggo Kann. On the approximability of np-complete optimization problems. PhD thesis,
Department of Numerical Analysis and Computing Science, Royal Institute of Technology,
Stockholm.
Nissan Lev-Tov and David Peleg. Polynomial time approximation schemes for base
station coverage with minimum total radii. Computer Networks, 47(4):489–501, 2005.
Satu Elisa Schaeffer. Graph clustering. Computer Science Review, 1(1):27–64, 2007.
Mohammad Salavatipour Zachary Friggstad, Mohsen Rezapour. Local search yields a
ptas for k-means in doubling metrics. In FOCS, to appear, 2016.

XX:19

