The Non-Uniform k-Center Problem
Deeparnab Chakrabarty

Prachi Goyal

Ravishankar Krishnaswamy

arXiv:1605.03692v2 [] 13 May 2016

Microsoft Research, India
dechakr,t-prgoya,rakri@microsoft.com

Abstract
In this paper, we introduce and study the Non-Uniform k-Center (NUkC) problem. Given a finite
metric space (X, d) and a collection of balls of radii {r1 ≥ · · · ≥ rk }, the NUkC problem is to find a
placement of their centers on the metric space and find the minimum dilation α, such that the union of
balls of radius α · ri around the ith center covers all the points in X. This problem naturally arises as a
min-max vehicle routing problem with fleets of different speeds.
The NUkC problem generalizes the classic k-center problem when all the k radii are the same (which
can be assumed to be 1 after scaling). It also generalizes the k-center with outliers (kCwO for short)
problem when there are k balls of radius 1 and ` balls of radius 0. There are 2-approximation and
3-approximation algorithms known for these problems respectively; the former is best possible unless
P=NP and the latter remains unimproved for 15 years.
We first observe that no O(1)-approximation is to the optimal dilation is possible unless P=NP,
implying that the NUkC problem is more non-trivial than the above two problems. Our main algorithmic
result is an (O(1), O(1))-bi-criteria approximation result: we give an O(1)-approximation to the optimal
dilation, however, we may open Θ(1) centers of each radii. Our techniques also allow us to prove a simple
(uni-criteria), optimal 2-approximation to the kCwO problem improving upon the long-standing 3-factor.
Our main technical contribution is a connection between the NUkC problem and the so-called
firefighter problems on trees which have been studied recently in the TCS community. We show NUkC is
as hard as the firefighter problem. While we don’t know if the converse is true, we are able to adapt ideas
from recent works [3, 1] in non-trivial ways to obtain our constant factor bi-criteria approximation.

1

Introduction

Source location and vehicle routing problems are extremely well studied [19, 23, 9] in operations research. Consider the following location+routing problem: we are given a set of k ambulances with speeds
s1 , s2 , . . . , sk respectively, and we have to find the depot locations for these vehicles in a metric space (X, d)
such that any point in the space can be served by some ambulance as fast as possible. If all speeds were the
same, then we would place the ambulances in locations S such that maxv∈X d(v, S) is minimized – this is
the famous k-center problem. Differing speeds, however, leads to non-uniformity, thus motivating the titular
problem we consider.
Definition 1.1 (The Non-Uniform k-Center Problem (NUkC)). The input to the problem is a metric space
(X, d) and a collection of k balls of radii {r1 ≥ r2 ≥ · · · ≥ rk }. The objective is to find a placement C ⊆ X
of the centers of these balls, so as to minimize the dilation parameter α such that the union of balls of radius
α · ri around the ith center covers all of X. Equivalently, we need to find centers {c1 , . . . , ck } to minimize
i)
maxv∈X minki=1 d(v,c
ri .
1

As mentioned above, when all ri ’s are the same (and equal to 1 by scaling), we get the k-center problem.
The k-center problem was originally studied by Gonzalez [10] and Hochbaum and Shmoys [13] as a clustering
problem of partitioning a metric space into different clusters to minimize maximum intra-cluster distances.
One issue (see Figure 1 for an illustration and refer to [11] for a more detailed explanation) with k-center
(and also k-median/means) as an objective function for clustering is that it favors clusters of similar sizes
with respect to cluster radii. However, in presence of qualitative information on the differing cluster sizes,
the non-uniform versions of the problem can arguably provide more nuanced solutions. One such extreme
special case was considered as the “clustering with outliers” problem [7] where some fixed number/fractions
of points in the metric space need not be covered by the clusters. In particular, Charikar et al [7] consider
(among many problems) the k-center with outlier problem (kCwO, for short) and show a 3-approximation
for this problem. It is easy to see that kCwO is a special case of the NUkC problem when there are k balls of
radius 1 and ` (the number of outliers) balls of radius 0.
Motivated by the aforementioned reasons (both from facility location as well as from clustering settings), we investigate the worst-case complexity of the NUkC problem. Gonzalez [10] and Hochbaum and
Shmoys [13] give 2-approximations for the k-center problem, and also show that no better factor is possible
unless P = NP. Charikar et al [7] give a 3-approximation for the kCwO problem, and this has been the best
factor known for 15 years. Given these algorithms, it is natural to wonder if a simple O(1)-approximation
exists for the NUkC problem. In fact, our first result shows a qualitative distinction between NUkC and these
problems: constant-approximations are impossible for NUkC unless P=NP.
Theorem 1.2. For any constant c ≥ 1, the NUkC problem does not admit a c-factor approximation unless
P = N P , even when the underlying metric is a tree metric.
The hardness result is by a reduction from the so-called resource minimization for fire containment
problem on trees (RMFC-T, in short), a variant of the firefighter problem. To circumvent the above hardness,
we give the following bi-criteria approximation algorithm which is the main result of the paper, and which
further highlights the connections with RMFC-T since our algorithms heavily rely on the recent algorithms
for RMFC-T [3, 1]. An (a, b)-factor bi-criteria algorithm for NUkC returns a solution which places at most
a balls of each type (thus in total it may use as many as a · k balls), and the dilation is at most b times the
optimum dilation for the instance which places exactly one ball of each type.
Theorem 1.3. There is an (O(1), O(1))-factor bi-criteria algorithm for the NUkC problem.

Figure 1: The left figure shows the dataset, the middle figure shows a traditional k-center clustering, and the
right figure depicts a non-uniform clustering
2

Furthermore, as we elucidate below, our techniques also give uni-criteria results when
√ the number of
distinct radii is 2. In particular, we get a 2-approximation for the kCwO problem and a (1+ 5)-approximation
when there are only two distinct types of radii.
Theorem 1.4. There is a 2-approximation for the kCwO problem.
√
Theorem 1.5. There is a (1 + 5)-approximation for the NUkC problem when the number of distinct radii
is at most 2.

1.1

Discussion on Techniques

Our proofs of Theorems 1.2 and 1.3 shows a strong connection between NUkC and the so-called resource
minimization for fire containment problem on trees (RMFC-T, in short). This connection is one of the main
findings of the paper, so we first formally define this problem.
Definition 1.6 (Resource Minimization for Fire Containment on Trees (RMFC-T)). Given a rooted tree T as
input, the goal is to select a collection of non-root nodes N from T such that (a) every root-leaf path has
at least one vertex from N , and (b) maxt |N ∩ Lt | is minimized, where Lt is the tth-layer of T , that is, the
vertices of T at exactly distance t from the root.
To understand the reason behind the name, consider a fire starting at the root spreading to neighboring
vertices each day; the RMFC-T problem minimizes the number of firefighters needed per day so as to prevent
the fire spreading to the leaves of T .
It is NP-hard to decide if the optimum of RMFC-T is 1 or not [8, 17]. Given any RMFC-T instance
and any c > 1, we construct an NUkC instance on a tree metric such that in the “yes” case there is always
a placement with dilation = 1 which covers the metric, while in the “no” case even a dilation of c doesn’t
help. Upon understanding our hardness construction, the inquisitive reader may wonder if the reduction
also works in the other direction, i.e., whether we can solve NUkC using a reduction to RMFC-T problem.
Unfortunately, we do not know if this is true even for two types of radii. However, as we explain below we
still can use positive results for the RMFC-T problem to design good algorithms for the NUkC problem.
Indeed, we start off by considering the natural LP relaxation for the NUkC problem and describe an
LP-aware reduction of NUkC to RMFC-T. More precisely, given a feasible solution to the LP-relaxation for
the given NUkC instance, we describe a procedure to obtain an instance of RMFC-T defined by a tree T ,
with the following properties: (i) we can exhibit a feasible fractional solution for the LP relaxation of the
RMFC-T instance, and (ii) given any feasible integral solution to the RMFC-T instance, we can obtain a
feasible integral solution to the NUkC instance which dilates the radii by at most a constant factor. Therefore,
an LP-based ρ-approximation to RMFC-T would immediately imply (ρ, O(1))-bicriteria approximation
algorithms for NUkC. This already implies Theorem 1.4 and Theorem 1.5 since the corresponding RMFC-T
instances have no integrality gap. Also, using a result of Chalermsook and Chuzhoy [3], we directly obtain
an (O(log∗ n), O(1))-bicriteria approximation algorithm for NUkC.
Here we reach a technical bottleneck: Chalermsook and Chuzhoy [3] also show that the integrality
gap of the natural LP relaxation for RMFC-T is Ω(log∗ n). When combined with our hardness reduction
in Theorem 1.2 , this also implies a (Ω(log∗ n), c) integrality gap for any constant c > 1 for the natural LP
relaxation for NUkC. That is, even if we allow a violation of c in the radius dilation, there is a Ω(log∗ n)integrality gap in terms of the violation in number of balls opened of each type.
However, very recently, Adjiashvili, Baggio and Zenklusen [1] show an improved O(1)-approximation
for the RMFC-T problem. At a very high level, the main technique in [1] is the following. Given an
3

RMFC-T instance, they carefully and efficiently “guess” a subset of the optimum solution, such that the
natural LP-relaxation for covering the uncovered leaves has O(1)-integrality gap. However, this guessing
procedure crucially uses the tree structure of T in the RMFC-T problem. Unfortunately for us though, we get
the RMFC-T tree only after solving the LP for NUkC, which already has an Ω(log∗ n)-gap! Nevertheless,
inspired by the ideas in [1], we show that we can also efficiently preprocess an NUkC instance, “guessing”
the positions of a certain number of balls in an optimum solution, such that the standard LP-relaxation for
covering the uncovered points indeed has O(1)-gap. We can then invoke the LP-aware embedding reduction
to RMFC-T at this juncture to solve our problem. This is quite delicate, and is the most technically involved
part of the paper.

1.2

Related Work and Open Questions

The k-center problem [10, 13] and the k-center with outliers [7] probems are classic problems in approximation algorithms and clustering. These problems have also been investigated under various settings such as the
incremental model [5, 22], streaming model [4, 22], and more recently in the map-reduce model [14, 21].
Similarly, the k-median [6, 15, 20, 2] and k-means [15, 16, 12, 18] problems are also classic problems studied
extensively in approximation algorithms and clustering. The generalization of k-median to a routing+location
problem was also studied recently [9]. It would be interesting to explore the complexity of the non-uniform
versions of these problems. Another direction would be to explore if the new non-uniform model can be
useful in solving clustering problems arising in practice.

2

Hardness Reduction

In this section, we prove Theorem 1.2 based on the following NP-hardness [17] for RMFC-T.
Theorem 2.1. [17] Given a tree T whose leaves are at the same distance from the root, it is NP-hard to
distinguish between the following two cases. YES: There is a solution to the RMFC-T instance of value 1.
NO: All solutions to the RMFC-T instance has value 2.
Given an RMFC-T instance defined by tree T , we now describe the construction of our NUkC instance.
Let h be the height of the tree, and let Lt denote the vertices of the tree at distance exactly t from the root. So,
the leaves constitute Lh since all leaves are at the same distance from the root. The NUkC instance, I(T ), is
defined by the metric space (X, d), and a collection of balls. The points in our metric space will correspond to
the leaves of the tree, i.e., X = Lh . To define the metric, we assign a weight d(e) = (2c + 1)h−i+1 for each
edge whose one endpoint is in Li and the other in Li−1 ; we then define d be the shortest-path metric on X
induced by this weighted tree. Finally, we set k = h, and define the k radii r1 ≥ r2 ≥ . . . ≥ rk iteratively as
follows: define rk := 0, and for k ≥ i > 1, set ri−1 := (2c + 1) · ri + 2(2c + 1). This completes the NUkC
instance. Before proceeding we make the simple observation: for any two leaves u and u0 with lca v ∈ Lt , we
have d(u, u0 ) = 2(2c + 1 + (2c + 1)2 + · · · + (2c + 1)h−t ) = rt . The following lemma proves Theorem 1.2.
Lemma 2.2. If T is the YES case of Theorem 2.1, then I(T ) has optimum dilation = 2. If T is the NO case
of 2.1, then I(T ) has optimum dilation ≥ 2c.
Proof. Suppose T is in the YES case, and there is a solution to RMFC-T which selects at most 1 node from
each level Lt . If v ∈ Lt is selected, then select a center cv arbitrarily from any leaf in the sub-tree rooted at v
and open the ball of radius rt . We now need to show all points in X = Lh are covered by these balls. Let u

4

be any leaf; there must be a vertex v in some level Lt in u’s path to the root such that a ball of radius rt is
opened at cv . However, d(u, cv ) ≤ d(u, v) + d(v, cv ) = 2rt and so the ball of radius 2rt around cv covers u.
Now suppose T is in the NO case, and the NUkC instance has a solution with optimum dilation < 2c.
We build a good solution for the RMFC-T instance N as follows: suppose the NUkC solution opens the
radius < 2c · rt ball around center u. Let v be the vertex on the u-root path appearing in level Lt . We then
pick this node in N . Observe two things: first, this ball covers all the leaves in the sub-tree rooted at v since
rt ≥ d(u, u0 ) for any such u0 . Furthermore, since the NUkC solution has only one ball of each radius, we get
that |N ∩ Lt | ≤ 1. Finally, since d(u, w) ≥ 2c · rt for all leaves w not in the sub-tree rooted at v, the ball of
radius rt around u doesn’t contain any leaves other than those rooted at v. Contra-positively, since all leaves
w are covered in some ball, every leaf must lie in the sub-tree of some vertex picked in N . That is, N is a
solution to RMFC-T with value = 1 contradicting the NO case.

3

LP-aware reduction from NUkC to RMFC-T

For reasons which will be apparent soon, we consider instances I of NUkC counting multiplicites. That
is, we consider
instance to be a collection of tuples (k1 , r1 ), . . . , (kh , rh ) to indicate there are ki balls of
Pan
h
radius ri . So t=1 kt = k. Intuitively, the reason we do this is that if two radii rt and rt+1 are “close-by”
then it makes sense to round up rt+1 to rt and increase kt , losing only a constant-factor loss in the dilation.
LP-relaxation for NUkC. We now state the natural LP relaxation for a given NUkC instance I. For each
point p ∈ X and radius type ri , we have an indicator variable xp,i ≥ 0 for whether we place a ball of radius ri
centered at p. By doing a binary search on the optimal dilation and scaling, we may assume that the optimum
dilation is 1. Then, the following linear program must be feasible. Below, we use B(q, ri ) to denote the set
of points within distance ri from q.
∀p ∈ X,
∀t ∈ 1, · · · , h

h
X

X

t=1

q∈B(p,rt )

X

xq,t

≥1

(NUkC LP)

≤ kt

xp,t

p∈X

LP-relaxation for RMFC-T. Since we reduce fractional NUkC to fractional RMFC-T, we now state the
natural LP relaxation for RMFC-T on a tree T of depth h + 1. In fact, we will work with the following
budgeted-version of RMFC-T (which is equivalent to the original RMFC-T problem — for a proof, see [1]):
Instead of minimizing the maximum number of “firefighters” at any level t (that is |N ∩ Lt | where N is
the chosen solution), suppose we specify a budget limit of kt on |N ∩ Lt |. The goal is the minimize the
maximum dilation of these budgets. Then the following is a natural LP relaxation for the budgeted RMFC-T
problem on trees. Here L = Lh is the set of leaves, and Lt are the layer t-nodes. For a leaf node v, let Pv
denote the vertex set of the unique leaf-root path excluding the root.
min α
X
yu ≥ 1

∀v ∈ L,

u∈Pv

X

∀t ∈ 1, · · · , h

u∈Lt

5

yu

≤ α · kt

(RMFC-T LP)

The LP-aware Reduction to Tree metrics. We now describe our main reduction algorithm, which takes
as input an NUkC instance I = {(X, d); (k1 , r1 ), . . . , (kh , rh )} and a feasible solution x to NUkC LP, and
returns a budgeted RMFC-T instance IT defined by a tree T along with budgets for each level, and a feasible
solution y to RMFC-T LP with dilation 1. The tree we construct will have height h + 1 and the budgeted
RMFC-T instance will have budgets precisely kt at level 1 ≤ t ≤ h, and the budget for the leaf level is 0.
For clarity, throughout this section we use the word points to denote elements of the metric space in I, and
the word vertices/nodes to denote the tree nodes in the RMFC-T instance that we construct. We build the
tree T in a bottom-up manner, where in each round, we pick a set of far-away representative points (the
distance scale increases as we move up the tree) and cluster all points to their nearest representative. This
is similar to a so-called clustering step in many known algorithms for facility location (see, e.g. [6]), but
whereas an arbitrary set of far-away representatives would suffice in the facility location algorithms, we need
to be careful in how we choose this set to make the overall algorithm work.
Formally, each vertex of the tree T is mapped to some point in X, and we denote the mapping of the
vertices at level t by ψt : Lt → X. We will maintain that each ψt will be injective, so ψt (u) 6= ψt (v) for
u 6= v in Lt . So, ψt−1 is well defined for the range of ψt .
The complete algorithm runs in rounds h + 1 to 2 building the tree one level per round. To begin with,
the ψh+1 mapping is an arbitrary bijective mapping between L := Lh+1 , the set of leaves of the tree, and the
points of X (so, in particular, |L| = |X|). We may assume it to be the identity bijection. In each round t, the
range of the mappings become progressively smaller, that is1 , P
ψt (Lt ) ⊇ ψt−1 (Lt−1 ). We call ψt (Lt ) as the
winners at level t. We now describe round t. Let Covt (p) := q∈B(p,rt ) xq,t denote
Pthe fractional amount
the point p is covered by radius rt balls in the solution x. Also define Cov≥t (p) := s≥t Covs (p) denoting
the fractional amount p is covered by radius rt or smaller balls. Let Covh+1 (p) = 0 for all p.
Algorithm 1 Round t of the LP-aware Reduction.
Input: Level Lt , subtrees below Lt , the mappings ψs : Ls → X for all t ≤ s ≤ h.
Output: Level Lt−1 , the connections between Lt−1 and Lt , and the mapping ψt−1 .
Define A = ψt (Lt ) the set of points who are winners at level t.
while A 6= ∅ do
(a) Choose the point p ∈ A with minimum coverage Cov≥t (p).
(b) Let N (p) := {q ∈ A : d(p, q) ≤ 2rt−1 } be the set of all nearby points in A to p.
(c) Create a new tree vertex w ∈ Lt−1 corresponding to p and set ψt−1 (w) := p. Call p a winner at
level t − 1, and each q ∈ N (p) ⊆ A a loser to p at this level.
(d) Create edge (w, v) for tree vertices v ∈ ψt−1 (N (p)) associated with N (p) at level t.
(e) Set A ← A \ (N (p)).
(f) Set yw = Covt−1 (p).
end while
Finally, we add a root vertex and connect it to all vertices in L1 . This gives us the final tree T and a
solution y which assigns a value to all non-leaf, non-root vertices of the tree T . The following claim asserts
well-definedness of the algorithm.
Lemma 3.1. The solution y is a feasible solution to RMFC-T LP on IT with dilation 1.
Proof. The proof is via two claims for the two different set of inequalities.
1

We are using the notation ψ(X) :=

S

x∈X

ψ(x).

6

Claim 3.2. For all 1 ≤ t ≤ h, we have

P

w∈Lt

yw ≤ kt .

Proof.
Fix t. Let
P
P Wt ⊆ X denote the winners at level t, that is, Wt = ψt (Lt ). By definition of the algorithm,
y
=
w∈Lt w
p∈Wt Covt (p). Now note that for any two points p, q ∈ Wt , we have B(p, rt ) ∩ B(q, rt ) = ∅.
To see this, consider the first point which enters A in the (t + 1)th round when Lt was being formed. If
this is p, then all points in the radius
t ball are deleted from A. Since the balls are disjoint, the second
P 2rP
inequality of NUkC LP implies p∈Wt q∈B(p,rt ) xq,t ≤ kt . The second summand in the LHS is precisely
Covt (p).
P
Claim 3.3. For any leaf node w ∈ L, we have v∈Pw yv ≥ 1.
Proof. We start with an observation. Fix a level t and a winner point p ∈ Wt . Let u ∈ Lt such that ψt (u) = p.
Since Wt ⊆ Wt+1 ⊆ · · · ⊆ Wh , there is a leaf v in the subtree rooted at u corresponding to p. Moreover, by
0
0
the
P way we formed our tree edges in step (d), we have that ψs (w ) = p for all w in the (u, v)-path and hence
w0 ∈[u,v]-path yw0 is precisely Cov≥t (p).
Now, for contradiction, suppose there is some leaf corresponding to, say point p, such that the root-leaf
path has total y-assignment less than 1. Then, pick the point, among all such unsatisfied points p, who appears
in a winning set Wt with t as small as possible.
By the preceding observation, the total y-assignment p receives on its path from level h to level t is
−1
exactly Cov≥t (p). Moreover, suppose p loses to q at level t − 1, i.e., ψt−1 (p) is a child of ψt−1
(q). In
particular, it means that q has also been a winner up to level t and so the total y-assignment on q’s path
−1
upto level t is also precisely Cov≥t (q). Additionally, since ψt−1
(q) became the parent node for ψt−1 (p), we
know that Cov≥t (q) ≤ Cov≥t (p) due to the way we choose winners in step (a) of the while loop. Finally,
by our maximality assumption on p, we know that q is fractionally satisfied by the y-solution. Therefore,
there is fractional assignment of at least (1 − Cov≥t (q)) on q’s path from nodes in level t − 1 to level 1.
Putting these observations together, we get that the total fractional assignment on p’s root-leaf path is at least
Cov≥t (p) + (1 − Cov≥t (q)) ≥ 1, which results in the desired contradiction.

The following lemma shows that any good integral solution to the RMFC-T instance IT can be converted
to a good integral solution for the NUkC instance I.
Lemma 3.4. Suppose there exists a feasible solution N to IT such that for all 1 ≤ t ≤ h, |N ∩ Lt | ≤ αkt .
Then there is a solution to the NUkC instance I that opens, for each 1 ≤ t ≤ h, at most αkt balls of radius
≤ 2r≥t ,where r≥t := rt + rt+1 + · · · + rh .
Proof. Construct the NUkC solution as follows: for level 1 ≤ t ≤ h and every vertex w ∈ N ∩ Lt , place
the center at ψt (w) of radius 2r≥t . We claim that every point in X is covered by some ball. Indeed, for any
p ∈ X, look at the leaf v = ψh+1 (p), and let w ∈ N be a node in the root-leaf path. Let w ∈ Lt for some t.
Now observe that d(p, ψt (w)) ≤ 2r≥t ; this is because for any edge (u0 , v 0 ) in the tree where u0 is in Lt and
is the parent of v 0 , we have that d(ψt+1 (v 0 ), ψt+1 (u0 )) < 2rt .
This completes the reduction, and we now prove a few results which follow easily from known results about
the firefighter problem.
Theorem 3.5. There is a polynomial time (O(log∗ n), 8)-bi-criteria algorithm for NUkC.

7

Proof. Given any instance I of NUkC, we first club the radii to the nearest power of 2 to get an instance I 0
with radii (k1 , r1 ), · · · , (kh , rh ) such that an (a, b)-factor solution for I 0 is an (a, 2b)-solution for I. Now,
by scaling, we assume that the optimal dilation for I 0 is 1; we let x be the feasible solution to the NUkC LP.
Then, using Algorithm 1, we can construct the tree IT0 and a feasible solution y to the RMFC-T LP. We can
now use the following theorem of Chalermsook and Chuzhoy [3]: given any feasible solution to the RMFC-T
LP, we can obtain a feasible set N covering all the leaves such that for all t, |N ∩ Lt | ≤ O(log∗ n)kt . Finally,
we can apply Lemma 3.4 to obtain a (O(log∗ n), 4) solution to I 0 (since r≥t ≤ 2rt ).
Proof of Theorem 1.4 and Theorem 1.5. We use the following claim regarding the integrality gap of RMFC-T
LP for depth 2 trees.
Claim 3.6. When h = 2 and kt ’s are integers, given any fractional solution to RMFC-T LP, we can find a
feasible integral solution as well.
Proof. Given a feasible solution y to RMFC-T LP, we need to find a set N such that |N ∩ Lt | ≤ kt for
t = 1, 2. There must exist at least one vertex w ∈ L1 such that yw ∈ (0, 1) for otherwise the solution y
is trivially integral. If only one vertex w ∈ L1 is fractional, then since k1 is an integer, we can raise this
yw to be an integer as well. So at least two vertices w and w0 in L1 are fractional. Now, without loss of
generality, let us assume that |C(w)| ≥ |C(w0 )|, where C(w) is the set of children of w. Now for some small
0 := y + , y 0 := y 0 − , ∀c ∈ C(w), y 0 := y − , and
constant 0 <  < 1, we do the following: yw
w
c
w
c
w0
∀c ∈ C(w0 ), yc0 := yc + . Note that y(L1 ) remains unchanged, y(L2 ) can only decrease, and root-leaf paths
still add to at least 1. We repeat this till we rule out all fractional values.
To see the proof of Theorem 1.4, note that an instance of the k-center with outliers problem is an NUkC
instance with (k, 1), (`, 0), that is, r1 = 1 and r2 = 0. We solve the LP relaxation and obtain the tree and an
RMFC-T solution. The above claim implies a feasible integral solution to RMFC-T since h = 2, and finally
note that r≥1 = r1 for kCwO, implying we get a 2-factor approximation.
√
The proof of Theorem 1.5 is similar. If√r1 < θr2 where θ = ( 5 + 1)/2, then we simply run k-center
with k = k1√+ k2 . This gives a 2θ = 5 + 1-approximation. Otherwise, we apply Lemma 3.4 to get a
2(1 + 1θ ) = 5 + 1-approximation.
We end this section with a general theorem, which is an improvement over Lemma 3.4 in the case when
many of the radius types are close to each other, in which case r≥t could be much larger than rt . Indeed, the
natural way to overcome this would be to group the radius types into geometrically increasing values as we
did in the proof of Theorem 3.5. However, for some technical reasons we will not be able to bucket the radius
types in the following section, since we would instead be bucketing the number of balls of each radius type in
a geometric manner. Instead, we can easily modify Algorithm 1 to build the tree by focusing only on radius
types where the radii grow geometrically.
Theorem 3.7. Given an NUkC instance I = {M = (X, d), (k1 , r1 ), (k2 , r2 ), . . . , (kh , rh )} and an LP
solution x for NUkC LP, there is an efficient reduction which generates an RMFC-T instance IT and an LP
solution y to RMFC-T LP, such that the following holds:
(i) For any two tree vertices w ∈ Lt and v ∈ Lt0 where w is an ancestor of v (which means t ≤ t0 ),
suppose p and q are the corresponding points in the metric space, i.e., p = ψt (w) and q = ψt0 (v), then
it holds that d(p, q) ≤ 8 · rt .

8

(ii) Suppose there exists a feasible solution N to IT such that for all 1 ≤ t ≤ h, |N ∩ Lt | ≤ αkt . Then
there is a solution to the NUkC instance I that opens, for each 1 ≤ t ≤ h, at most αkt balls of radius
at most 8 · rt .

3.1

Proof of Theorem 3.7

Both the algorithm as well as the proof are very similar, and we now provide them for completeness. At a
high level, the only difference occurs when we identify and propagate winners: instead of doing it for each
radius type, we identify barrier levels where the radius doubles, and perform the clustering step only at the
barrier levels. We now present the algorithm, which again proceeds in rounds h + 1, h, h − 1, . . . , 2, but
makes jumps whenever there are many clusters of similar radius type. To start with, define rh+1 = 0.
Algorithm 2 Round t of the Improved Reduction.
Input: Level Lt , subtrees below Lt , the mappings ψs : Ls → X for all t ≤ s ≤ h.
Output: Level Lt−1 , the connections between Lt−1 and Lt , and the mapping ψt−1 .
Let t0 = mins s.t.rs ≤ 2rt−1 be the type of the largest radius smaller than 2rt−1 .
Define A = ψt (Lt ) the set of points who are winners at level t.
while A 6= ∅ do
(a) Choose the point p ∈ A with minimum coverage Cov≥t (p).
(b) Let N (p) := {q ∈ A : d(p, q) ≤ 2rt0 } denote all points in A within 2rt0 from p.
(c) Create new vertices wt−1 , . . . , wt0 −1 ∈ Lt−1 , . . . , Lt0 −1 levels respectively, all corresponding to p,
i.e., set ψi (w) := p for all t0 − 1 ≤ i ≤ t − 1. Connect each pair of these vertices in successive levels
with edges. Call p a winner at levels t − 1, . . . , t0 − 1.
(d) Create edge (wt−1 , v) for vertices v ∈ ψt−1 (N (p)) associated with N (p) at level t.
(f) Set A ← A \ (N (p)).
(g) Set ywi = Covi (p) for all t − 1 ≤ i ≤ t0 − 1.
end while
Jump to round t0 − 1 of the algorithm. Add t0 − 1 to the set of barrier levels
Our proof proceeds almost in an identical manner to those of Lemmas 3.1 and 3.4, but now our tree has
an additional property that for any two nodes u ∈ Li and v ∈ Li0 where u is an ancestor of v, the distance
between the corresponding points in the metric space p = ψi (u) and q = ψi0 (v) is at most d(p, q) ≤ 8ri ,
which was the property not true in the earlier reduction. This is easy to see because as we traverse a tree
path from u to v, notice that each time we change winners, the distance between the corresponding points in
the metric space decreases geometrically. This proves property (i) of Theorem 3.7. With this in hand, the
remaining proofs to prove the second property are almost identical to the ones in Section 3 and we sketch
them below for completeness.
Lemma 3.8. The solution y is a feasible solution to RMFC-T LP on IT with dilation 1.
Proof. The proof is via two claims for the two different set of inequalities.
P
Claim 3.9. For all 1 ≤ t ≤ h, we have w∈Lt yw ≤ kt .
Proof. Fix a barrier
Plevel t. Let W
Pt ⊆ X denote the winners at level t, that is, Wt = ψt (Lt ). By definition
of the algorithm, w∈Lt yw = p∈Wt Covt (p). Now note that for any two points p, q ∈ Wt , we have
B(p, rt ) ∩ B(q, rt ) = ∅. To see this, consider the first point which enters A in the round (corresponding to the
9

previous barrier) when Lt was being formed. If this is p, then all points in the
P radiusP2rt ball is deleted from
A. Since the balls are disjoint, the second inequality of NUkC LP implies p∈Wt q∈Bt (p) xq,t ≤ kt . The
second summand in the LHS is the definition of Covt (p). The same argument holds for all levels t between
two consecutive barrier levels t1 and t2 s.t. t1 > t2 , as the winner set remains the same, and the radius rt is
only smaller than the radius rt2 at the barrier t2 .
P
Claim 3.10. For any leaf node w ∈ L, we have v∈Pw yv ≥ 1.
Proof. This proof is identical to that of Claim 3.3, and we repeat it for completeness. Fix a level t and a
winner point p ∈ Wt . Let u ∈ Lt such that ψt (u) = p. Since Wt ⊆ Wt+1 ⊆ · · · ⊆ Wh , there is a leaf v in
the subtree rooted at u corresponding to p. Moreover, by the
Pway we formed our tree edges in step (d), we
have that ψs (w) = p for all w0 in the (u, v)-path and hence w0 ∈[u,v]-path yw0 is precisely Cov≥t (p).
Now, for contradiction, suppose there is some leaf corresponding to, say point p, such that the root-leaf
path has total y-assignment less than 1. Then, pick the point, among all such unsatisfied points p, who appears
in a winning set Wt with t as small as possible.
By the preceding observation, the total y-assignment p receives on its path from level h to level t is
−1
exactly Cov≥t (p). Moreover, suppose p loses to q at level t − 1, i.e., ψt−1 (p) is a child of ψt−1
(q). In
particular, it means that q has also been a winner up to level t and so the total y-assignment on q’s path up
−1
to level t is also precisely Cov≥t (q). Additionally, since ψt−1
(q) became the parent node for ψt−1 (p), we
know that Cov≥t (q) ≤ Cov≥t (p) due to the way we choose winners in step (a) of the while loop. Finally,
by our maximality assumption on p, we know that q is fractionally satisfied by the y-solution. Therefore,
there is fractional assignment of at least (1 − Cov≥t (q)) on q’s path from nodes in level t − 1 to level 1.
Putting these observations together, we get that the total fractional assignment on p’s root-leaf path is at least
Cov≥t (p) + (1 − Cov≥t (q)) ≥ 1, which results in the desired contradiction.

Finally, the following lemma shows that any good integral solution to the RMFC-T instance IT can be
converted to a good integral solution for the NUkC instance I.
Lemma 3.11. Suppose there exists a feasible solution N to IT such that for all 1 ≤ t ≤ h, |N ∩ Lt | ≤ αkt .
Then there is a solution to the NUkC instance I that opens, for each 1 ≤ t ≤ h, at most αkt balls of radius
at most 8rt .
Proof. Construct the NUkC solution as follows: for level 1 ≤ t ≤ h and every vertex w ∈ N ∩ Lt , place
the center at ψt (w) of radius 8 · rt . We claim that every point in X is covered by some ball. Indeed, for any
p ∈ X, look at the leaf v = ψh+1 (p), and let w ∈ N be a node in the root-leaf path which covers it in the
instance IT . By property (i) of Theorem 3.7, we have that the distance between ψt (w) and p is at most 8 · rt ,
and hence the ball of radius 8 · rt around ψt (w) covers p. The number of balls of radius type t is trivially at
most αkt .

4

Getting an (O(1), O(1))-approximation algorithm

In this section, we improve our approximation factor on the number of clusters from O(log∗ n) to O(1),
while maintaining a constant-approximation in the radius dilation. As mentioned in the introduction, this
requires more ideas since using NUkC LP one cannot get any factor better than (O(log∗ n), O(1))-bicriteria

10

approximation since any integrality gap for RMFC-T LP translates to a (Ω(log∗ n), Ω(1)) integrality gap
for NUkC LP.
Our algorithm is heavily inspired by the recent paper of Adjiashvili et al [1] who give an O(1)approximation for the RMFC-T problem. In fact, the structure of our algorithms follows the same three
“steps” of their algorithm. Given an RMFC-T instance, [1] first “compress” the input tree to get a new tree
whose depth is bounded; secondly, [1] give a partial rounding result which saves “bottom heavy” leaves, that
is, leaves which in the LP solution are covered by nodes from low levels; and finally, Adjiashvili et al [1] give
a clever partial enumeration algorithm for guessing the nodes from the top levels chosen by the optimum
solution. We also proceed in these three steps with the first two being very similar to the first two steps in [1].
However, the enumeration step requires new ideas for our problem. In particular, the enumeration procedure
in [1] crucially uses the tree structure of the firefighter instance, and the way our reduction generates the
tree for the RMFC-T instance is by using the optimal LP solution for the NUkC instance, which in itself
suffers from the Ω(log∗ n) integrality gap. Therefore, we need to devise a more sophisticated enumeration
scheme although the basic ideas are guided by those in [1]. Throughout this section, we do not optimize for
the constants.

4.1

Part I: Radii Reduction

In this part, we describe a preprocessing step which decreases the number of types of radii. This is similar to
Theorem 5 in [1].
Theorem 4.1. Let I be an instance of NUkC with radii {r1 , r2 , · · · , rk }. Then we can efficiently construct a
new instance Ib with radii multiplicities (k0 , rb0 ), ..., (kL , rbL ) and L = Θ(log k) such that:
(i) ki := 2i for all 0 ≤ i < L and kL ≤ 2L .
b
(ii) If the NUkC instance I has a feasible solution, then there exists a feasible solution for I.
b we can efficiently obtain a (3α, β)-bicriteria solution to I.
(iii) Given an (α, β)-bicriteria solution to I,
Proof. For an instance I, we construct the compressed instance Ib as follows. Partition the radii into Θ(log k)
b we simply round up all
classes by defining barriers at rbi = r2i for 0 ≤ i ≤ blog kc. Now to create instance I,
i
i+1
the radii rj for 2 ≤ j < 2
to the value rbi = r2i . Notice that the multiplicity of rbi is precisely 2i (except
maybe for the last bucket, where there might be fewer radii rounded up than the budget allowed).
Property (i) is just by construction of instance. Property (ii) follows from the way we rounded up the
radii. Indeed, if the optimal solution for I opens a ball of radius rj around a point p, then we can open a
cluster of radius rbi around p, where i is such that 2i ≤ j < 2i+1 . Clearly the number of clusters of radius rbi
is at most 2i because OPT uses at most one cluster of each radius rj .
For property (iii), suppose we have a solution Sb for Ib which opens α2i clusters of radius βb
ri for all
0 ≤ i ≤ L. Construct a solution S for I as follows. For each 1 ≤ i ≤ L, let Ci denote the set of centers
where Sb opens balls of radius βb
ri . In the solution S, we also open balls at precisely these centers with 2α
i−1
balls of radius rj for every 2
≤ j < 2i . Since |Ci | ≤ α · 2i , we can open a ball at every point in Ci ;
furthermore, since j < 2i , we have rj ≥ rbi and so we cover whatever the balls from Sb covered.
Finally, we also open the α clusters (corresponding to i = 0) of radius βr1 = βb
r0 at the respective
centers C0 where Sb opens centers of radius rb0 . Therefore, the total number of clusters of radius type is at
most 2α with the exception of r1 , which may have 3α clusters.

11

4.2

Part II: Satisfying Bottom Heavy Points

One main reason why the above height reduction step is useful, is the following theorem from [1] for RMFC-T
instances on trees; we provide a proof sketch for completeness.
Theorem 4.2 ([1]). Given a tree T of height h and a feasible solution y to (RMFC-T LP), we can find a
feasible integral solution N to RMFC-T such that for all 1 ≤ t ≤ h, |N ∩ Lt | ≤ kt + h.
Proof. Let y be a basic feasible solution of (RMFC-T LP). Call a vertex v of the tree loose if yv > 0 and the
sum of y-mass on the vertices from v to the root (inclusive of v) is < 1. Let VL be the set of loose vertices of
the tree, and let VI be the set of vertices with yv = 1. Clearly N = VL ∪VI is a feasible solution: every leaf-toroot path either contains an integral vertex or at least two fractional vertices with the vertex closer to root being
loose. Next we claim that |VL | ≤ h; this proves the theorem since |N ∩ Lt | ≤ |VI ∩ Lt | + |VL | ≤ kt + |VL |.
The full proof can be found in Lemma 6, [1] – here is a high level sketch. There are |L| + h inequalities
in (RMFC-T LP), and so the number of fractional variables is at most |L| + h. We may assume there are no
yv = 1 vertices. Now, in every leaf-to-root path there must be at least 2 fractional vertices, and the one closest
to the leaf must be non-loose. If the closest fractional vertex to each leaf was unique, then that would account
for |L| fractional non-loose vertices implying the number of loose vertices must be ≤ h. This may not be
true; however, if we look at linearly independent set of inequalities that are tight, we can argue uniqueness as
a clash can be used to exhibit linear dependence between the tight constraints.
Theorem 4.3. Suppose we are given an NUkC instance Ib with radii multiplicities
(k0 , rb0 ), (k1 , rb1 ), . . . , (kL , rbL ) with budgets ki = 2i for radius type rbi , and an LP solution x to (NUkC LP)
b Let τ = log log L, and suppose X 0 ⊆ X be the points covered mostly by small radii, that is, let
for I.
Cov≥τ (p) ≥ 12 for every p ∈ X 0 . Then, there is an efficient procedure round which opens at most O(kt ) balls
of radius O(b
rt ) for τ ≤ t ≤ L, and covers all of X 0 .
Proof. The procedure round works as follows: we partition the points of X 0 into two sets, one set XU in
which the points receive at least 14 of the coverage by clusters of radius rbi where i ∈ {log log L, log log L +
1, . . . , log L}, and another set XB in which the points receive 14 coverage from clusters of levels t ∈ {log L +
P L
0
1, log L + 2, . . . , L}. More precisely, XU := {p ∈ X 0 : log
t=τ Covt (p) ≥ 1/4}, and XB = X \ XB .
Now consider the following LP-solution to (NUkC LP) for Ib restricted to XU : we scale x by a factor 4
and zero-out x on radii type rbi for i ∈
/ {log log L, . . . , log L}. By definition of XU this is a feasible fractional
solution; furthermore, the LP-reduction algorithm described in Section 3 will lead to a tree T of height ≤ log L
and fractional solution y for (RMFC-T LP) on T were each ki ≥ 2log log L = log L. Applying Theorem 4.2,
we can find an integral solution N with at most O(ki ) vertices at levels i ∈ {log log L, . . . , log L}. We can
then translate this solution back using Theorem 3.7 to NUkC and find O(kt ) clusters of radius O(b
rt ) to cover
all the points XU . A similar argument, when applied to the smaller radius types rbt for t ∈ {log L, . . . , L}
can cover the points in XB .
We now show how we can immediately also get a (very weakly) quasi-polynomial time O(1)-approximation
for NUkC. Indeed, if we could enumerate the set of clusters of radii rbt for 0 ≤ t < log log L, we can then
explicitly solve an LP where all the uncovered points need to be fractionally covered by only clusters of
radius type rbt for t ≥ log log L. We can then round this solution using Corollary 4.3 to obtain the desired
O(1)-approximation for the NUkC instance. Moreover, the time complexity of enumerating the optimal
clusters of radii rbt for 0 ≤ t < log log L is nO(log L) = nO(log log k) , since the number of clusters of radius at
least rblog log L is at most O(2log log L ) = O(log L). Finally, there was nothing special in the proof of Theorem 4.3 about the choice of τ = log log L — we could set t = log(q) L to be the q th iterated logarithm of
12

L, and obtain an O(q)-approximation. As a result, we get the following corollary. Note that this gives an
alternate way to prove Theorem 3.5.
Corollary 4.4. For any q ≥ 1, there exists an (O(q), O(1))-factor bicriteria algorithm for NUkC which
(q)
runs in nO(log k) time.

4.3

Part III: Clever Enumeration of Large Radii Clusters

In this section, we show how to obtain the (O(1), O(1))-factor bi-criteria algorithm. At a high level, our
algorithm tries to “guess” the centers2 A of large radius, that is rbi for i ≤ τ := log log L = log log log k,
which the optimum solution uses. However, this guessing is done in a cleverer way than in Corollary 4.4.
In particular, given a guess which is consistent with the optimum solution (the initial “null set” guess is
trivially consistent), our enumeration procedure generates a list of candidate additions to A of size at most
2τ ≈ poly log logk (instead of n), one of which is a consistent enhancement of the guessed set A. This
reduction in number of candidates also requires us to maintain a guess D of points where the optimum
solution doesn’t open centers. Furthermore, we need to argue that the “depth of recursion” is also bounded by
poly log logk; this crucially uses the technology developed in Section 3. Altogether, we get the total time is
at most (poly log logk)poly log logk = o(k) for large k.
We start with some definitions. Throughout, A and D represent sets of tuples of the form (p, t) where
p ∈ X and t ∈ {0, 1, . . . , τ }. Given such a set A, we associate a partial solution SA which opens a ball
of radius 22b
rt at the point p. For the sake of analysis, fix an optimum solution OPT. We say the set A is
consistent with OPT if for all (p, t) ∈ A, there exists a unique q ∈ X such that OPT opens a ball of radius
rbt at q and d(p, q) ≤ 11b
rt . In particular, this implies that SA covers all points which this OPT-ball covers.
We say the set D is consistent with OPT if for all (q, t) ∈ D, OPT doesn’t open a radius rbt ball at q (it may
open a different radius ball at q though). Given a pair of sets (A,D), we define the minLevel of each point p
as follows
minLevelA,D (p) := 1 + arg max{(q, t) ∈ D for all q ∈ B(p, rbt )}
t

If (A, D) is a consistent pair and minLevelA,D (p) = t, then this implies in the OPT solution, p is covered by
a ball of radius rbt or smaller.
Next, we describe a nuanced LP-relaxation for NUkC. Fix a pair of sets (A, D) as described above. Let
XG be the subset of points in X covered by the partial solution SA . Fix a subset Y ⊆ X \ XG of points.
Define the following LP.
∀p ∈ Y,
∀t ∈ 1, · · · , h

L
X

X

t=minLevel(p)

q∈B(p,b
rt )

X

xq,t

≤

xq,t

≥1

(LPNUkC (Y, A, D))

kt

q∈Y

∀(p, t) ∈ A,

xp,t = 1

The following claim encapsulates the utility of the above relaxation.
Claim 4.5. If (A, D) is consistent with OPT, then (LPNUkC (Y, A, D)) is feasible.
2

Actually, we end up guessing centers “close” to the optimum centers, but for this introductory paragraph this intuition is
adequate.

13

Proof. We describe a feasible solution to the above LP using OPT. Given OPT, define O to be the collection
of pairs (q, t) where OPT opens a radius rbt ball at point q. Note that the number of tuples in O with second
term t is ≤ kt .
Since A is consistent with OPT, for every (p, t) ∈ A, there exists a unique (q, t) ∈ O; remove all such
tuples from O. Define xq,t = 1 for all other remaining tuples. By the uniqueness property, we see the second
inequality of the LP is satisfied. We say a point p ∈ X is covered by (q, t) if p lies in the rbt -radius ball
around q. Since Y ⊆ X \ XG , and since the partial solution SA contains all points p which is covered by all
the removed (q, t) tuples, we see that every point p ∈ Y is covered by some remaining (q, t) ∈ O. Since
D is consistent with OPT, for every point p ∈ Y and t < minLevelA,D (p), if q ∈ B(p, rbt ) then (q, t) ∈
/ O.
Therefore, the first inequality is also satisfied.
Finally, for convenience, we define a forbidden set F := {(p, i) : p ∈ X, 1 ≤ i ≤ τ } which if added to
D disallows any large radii balls to be placed anywhere.
Now we are ready to describe the enumeration Algorithm 3. We start with A and D being null, and thus
vacuously consistent with OPT. The enumeration procedure ensures that: given a consistent (A, D) tuple,
either it finds a good solution using LP rounding (Step 10), or generates candidate additions (Steps 18–20) to
A or D ensuring that one of them leads to a larger consistent tuple.
Algorithm 3 Enum(A, D, γ)
1: Let XG = {p : ∃ (q, i) ∈ A s.t d(p, q) ≤ 22b
ri } denote points covered by SA .
2: if there is no feasible solution to LPNUkC (X \ XG , A, D) then
3:
Abort.
//Claim 4.5 implies (A, D) is not consistent.
4: else
5:
x∗ be a feasible solution to LPNUkC (X \ XG , A, D).
6: end if
7: Let XB = {u ∈ X \ XG : Cov≥τ (u) ≥ 21 } denote bottom-heavy points in x∗
8: Let SB be the solution implied by Theorem 4.3.
// This solution opens O(kt ) balls of radius O(b
rt ) for τ ≤ t ≤ L and covers all of XB .
9: Let XT = X \ (XG ∪ XB ) denote the top heavy points in x∗
10: if LPNUkC (XT , A, F ∪ D) has a feasible solution xT then
11:
By definition of F , in xT we have Cov≥τ (u) = 1 for all u ∈ XT .
12:
ST be the solution implied by Theorem 4.3.
// This solution opens O(kt ) balls of radius O(b
rt ) for τ ≤ t ≤ L and covers all of XT .
13:
Output (SA ∪ SB ∪ ST ). //This is a (O(1), O(1))-approximation for the NUkC instance.
14: else
15:
for every level 0 ≤ t ≤ τ do
16:
Let Ct = {p ∈ XT s.t minLevelA,D (p) = t}, the set of points in XT with minLevel t.
17:
Use the LP-aware reduction from Section 3 using x∗ and the set of points Ct to create tree Tt .
18:
for every winner p at level t in Tt do
19:
Enum(A ∪ {(p,St)}, D, γ − 1)
20:
Enum(A, D ∪ p0 ∈B(p,11brt ) {(p0 , t)}), γ − 1)
21:
end for
22:
end for
23: end if

14

Define γ0 := 4 log log k · log log log k. The algorithm is run with Enum(∅, ∅, γ0 ). The proof that we get
a polynomial time (O(1), O(1))-bicriteria approximation algorithm follows from three lemmas. Lemma 4.6
shows that if Step 10 is true with a consistent pair (A, D), then the output in Step 13 is a (O(1), O(1))approximation. Lemma 4.7 shows that indeed Step 10 is true for γ0 as set. Finally, Lemma 4.8 shows with
such a γ0 , the algorithm runs in polynomial time.
Lemma 4.6. If (A, D) is a consistent pair such that Step 10 is true, then the solution returned is an
(O(1), O(1))-approximation algorithm.
Proof. Since A is consistent with OPT, SA opens at most kt centers with radius ≤ 22b
rt for all 0 ≤ t ≤ τ .
By design, SB and ST open at most O(kt ) centers with radius ≤ O(rt ) for τ ≤ t ≤ L.
Lemma 4.7. Enum(∅, ∅, γ0 ) finds consistent (A, D) such that Step 10 is true.
Proof. For this we identify a particular execution path of the procedure Enum(A, D, γ), that at every point
maintains a tuple (A, D) that is consistent with OPT. At the beginning of the algorithm, A = ∅ and D = ∅,
which is consistent with OPT.
Now consider a tuple (A, D) that is consistent with OPT and let us assume that we are within the
execution path Enum(A, D, γ). Let X \ XG be the points not covered by A and let x∗ be a solution to
LPNUkC (X \ XG , A, D). If OPT covers all top-heavy points XT using only smaller radii, then this implies
LPNUkC (XT , A, F ∪ D) has a feasible solution implyin Step 10 is true. So, we may assume, there exists at
least one top-heavy point q ∈ XT that OPT covers using a ball radii ≥ rbτ around a center oq . In particular,
minLevelA,D (q) ≤ τ . Let q ∈ Ct and hence q belongs to Tt for some 0 ≤ t ≤ τ . Let p ∈ Pt be the level t
winner in Tt s.t q belongs to the sub-tree rooted at p in Ti ; p may or may not be q. We now show that there is
at least one recursive call where we make non-trivial progress in (A, D). Indeed, we do this in two cases:
case (A) If OPT opens a ball of radius rbt at a point o such that d(o, p) ≤ 11b
rt . In this case, Step 19 maintains
consistency. Furthermore, we can “charge” (p, t) uniquely to the point o with radius rbt . To see this, for
contradiction, let us assume that before arriving to the recursive call where (p, t) is added to A, some other
0
0
0
tuple (u, t) ∈ A , in an earlier recursive call with (A , D ) as parameters charged to (o, t). Then by definition
we know that d(u, o) ≤ 11b
rt implying d(u, p) ≤ 22b
rt . Then p would be in XG in all subsequent iterations,
contradicting that p ∈ XT currently.
case (B): Tf there is no (o, t) ∈ OPT with d(o, p) ≤ 11b
rt , then for all points p0 ∈ B(p, 11b
rt ) we can add
0
(p , t) to D. In this case, we follow the recursive call in Step 20.
To sum, we can definitely follow the recursive calls in the consistent direction; but how do we bound
the depth of recursion. In case (A), the measure of progress is clear – we increase the size of |A|, and it can
be argued (we do so below) the maximum size of A is at most poly log logk. Case (B) is subtler. We do
increase size of D, but D could grow as large as Θ(n). Before going to the formal proof, let us intuitively
argue what “we learn” in Case (B). Recall q is covered in OPT by a ball around the center oq . Since
minLevel(q) = t ≤ τ , by definition there is a point v ∈ B(q, rbt ) such that (v, t) ∈
/ D, and d(q, oq ) ≤ rbt .
Together, we get d(v, oq ) ≤ 2b
rt , that is, v ∈ B(oq , 2b
rt ). Now also note, since q lies in p’s subtree in Tt , by
construction of the trees, d(p, q) ≤ 8b
rt by property (i) of Theorem 3.7. Therefore, d(p, oq ) ≤ 9b
rt and in case
(B), for all points u ∈ B(oq , 2b
rt ) we put (u, t) in the set D in the next recursive call. This is “new info” since
for the current D we know that at least one point v ∈ B(oq , 2b
rt ), we had (v, t) ∈
/ D.
Formally, we define the following potential function. Let Oτ denote the centers in OPT around which
balls of radius rbj , j ≤ τ have been opened. Given the set D, for 0 ≤ t ≤ τ and for all o ∈ Oτ , define the

15

(D)

indicator variable Zo,t which is 1 if for all points u ∈ B(o, 2b
rt ), we have (u, t) ∈ D and 0 otherwise.
Φ(A, D) := |A| +

τ
XX

(D)

Zo,t

o∈Oτ t=0

Note that Φ(∅, ∅) = 0. From the previous paragraph, we conclude that in both case (A) or (B), the
potential increases by at least 1.
for any consistent A, D we can upper bound Φ(A, D) as follows.
PFinally,
τ
t
τ +1 = log L = log log k. The second term in Φ is at most
Since A is consistent, |A| ≤
t=0 2 ≤ 2
τ
+1
2
· τ = log L log log L. Thus, in at most 2 log log k · log log log k < γ0 steps we reach a consistent pair
(A, D) with Step 10 true.
Lemma 4.8. Enum(∅, ∅, γ0 ) runs in polynomial time for large enough k.
Proof. Each single call of Enum is clearly polynomial time, and so we bound the number of recursive
calls. Indeed, this number will be o(k). We first bound the number of recursive calls in a single execution
of Enum(A, D, γ). For a fixed tuple (A, D), Algorithm 3, constructs trees T0 , . . . , Tτ in Step 17, using
the reduction algorithm from Section 3. Let Ltj represent the set of nodes at level j in the tree Tt . Then
Pt = ψt (Ltt ) represents the set of points that are winners at level t in Tt . NowSfor any tree Tt , Algorithm 3
makes two recursive calls for each winner in Pt (Step 19-20). Let PAD = τt=0 Pt be the set of all the
winners that the algorithm considers in a single call to Enum(A, D, γ). The total number of recursive calls
in a single execution is therefore 2|PAD |. Now we claim that for a fixed tuple (A, D), the total number of
winners is bounded.
Claim 4.9. |PAD | ≤ 4 log log k · log log log k
Proof. Consider a tree Tt and the corresponding set Pt as defined above. We use y (t) to denote the RMFC-T
LP solution given along with the tree Tt given by the reduction algorithm in Section 3. Let p ∈ Pt be a
winner at level t (and consequently, at level τ also), and suppose it is mapped to tree vertices w at level t
and w0 at level τ . Then, by the way the tree was constructed and because p ∈ XT is top-heavy, we have
P
(t)
1
u∈[w,w0 ]−path yu ≥ 2 (Refer to the proof of Claim 3.3 for more clarity). So each winner at level t has a
1
path down to level τ with fractional coverage
2 . But the total fractional coverage in the top part of
Patτ least
t
the tree is at most the total budget, which is t=1 2 ≤ 2 log L ≤ 2 log log k. Therefore, |Pt | ≤ 4 log log k.
Adding for all 1 ≤ t ≤ τ , gives |PAD | ≤ 4 log log k · t ≤ 4 log log k · log log log k.
Since the recursion depth γ0 , the total number of recursive calls made to the Enum is loosely upper
bounded by γ0poly log logk = o(k), thus completing the proof.

References
[1] D. Adjiashvili, A. Baggio, and R. Zenklusen. Firefighting on trees beyond integrality gaps. CoRR,
abs/1601.00271, 2016.
[2] J. Byrka, T. Pensyl, B. Rybicki, A. Srinivasan, and K. Trinh. An improved approximation for k-median,
and positive correlation in budgeted optimization. Proceedings, ACM-SIAM Symposium on Discrete
Algorithms (SODA), 2015.

16

[3] P. Chalermsook and J. Chuzhoy. Resource minimization for fire containment. Proceedings, ACM-SIAM
Symposium on Discrete Algorithms (SODA), 2010.
[4] M. Charikar, L. O’ Callaghan, and R. Panigrahy. Better streaming algorithms for clustering problems.
ACM Symp. on Theory of Computing (STOC), 2003.
[5] M. Charikar, C. Chekuri, T. Feder, and R. Motwani. Incremental clustering and dynamic infomation
retrieval. ACM Symp. on Theory of Computing (STOC), 1997.
[6] M. Charikar, S. Guha, D. Shmoys, and E. Tardos. A constant-factor approximation algorithm for the
k-median problem. ACM Symp. on Theory of Computing (STOC), 1999.
[7] M. Charikar, S. Khuller, D. M. Mount, and G. Narasimhan. Algorithms for facility location problems
with outliers. Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2001.
[8] S. Finbow, A. King, G. MacGillivray, and R. Rizzi. The firefighter problem for graphs of maximum
degree three. Discrete Mathematics, 307(16):2094–2105, 2007.
[9] I. L. Goertz and V. Nagarajan. Locating depots for capacitated vehicle routing. Proceedings, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2011.
[10] T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer
Science, 38:293–306, 1985.
[11] S. Guha, R. Rastogi, and K. Shim. CURE: An efficient clustering algorithm for large databases.
Proceedings of SIGMOD, 1998.
[12] S. Har-Peled and S. Mazumdar. Coresets for k-means and k-median clustering and their applications.
ACM Symp. on Theory of Computing (STOC), 2004.
[13] D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of
operations research, 10(2):180–184, 1985.
[14] S. Im and B. Moseley. Fast and better distributed mapreduce algorithms for k-center clustering.
Proceedings, ACM Symposium on Parallelism in Algorithms and Architectures, 2015.
[15] K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k-median problems
using the primal-dual schema and lagrangian relaxation. J. ACM, 48(2):274 – 296, 2001.
[16] T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu. : A local search
approximation algorithm for k-means clustering. 2002.
[17] A. King and G. MacGillivray. The firefighter problem for cubic graphs. Discrete Mathematics,
310(3):614–621, 2010.
[18] A. Kumar, Y. Sabharwal, and S. Sen. A simple linear time (1 + )-approximation algorithm for k-means
clustering in any dimensions. Proceedings, IEEE Symposium on Foundations of Computer Science
(FOCS), 2004.
[19] G. Laporte. Location routing problems. In B. L. Golden and A. A. Assad, editors, Vehicle Routing:
Methods and Studies, pages 163–198. 1998.
17

[20] S. Li and O. Svensson. Approximating k-median via pseudo-approximation. ACM Symp. on Theory of
Computing (STOC), 2013.
[21] G. Malkomes, M. J. Kusner, W. Chen, K. Q. Weinberger, and B. Moseley. Fast distributed k-center
clustering with outliers on massive data. Advances in Neur. Inf. Proc. Sys. (NIPS), 2015.
[22] R. McCutchen and S. Khuller. Streaming algorithms for k-center clustering with outliers and with
anonymity. Proceedings, International Workshop on Approximation Algorithms for Combinatorial
Optimization Problems, 2008.
[23] H. Min, V. Jayaraman, and R. Srivastava. Combined location-routing problems: A synthesis and future
research directions. European Journal of Operational Research, 108:1–15, 1998.

18

