The Capacitated K-Center Problem

(Extended Abstract)

Samir Khuller 1 * and Yoram J. Sussmann 2 **

1 Dept. of Computer Science and UMIACS

University of Maryland, College Park, MD 20742
2 Dept. of Computer Science, University of Maryland, College Park, MD 20742

A b s t r a c t . The capacitated K-center problem is a fundamental facility

location problem, where we are asked to locate K facilities in a graph, and
to assign vertices to facilities, so as to minimize the maximum distance
from a vertex to the facility to which it is assigned. Moreover, each
facility may be assigned at most s vertices. This problem is known to
be NP-hard. We give polynomial time approximation algorithms for two
different versions of this problem that achieve approximation factors of
5 and 6. We also study some generalizations of this problem.

1 Introduction

The basic K-center problem is a fundamental facility location problem [17] and
is defined as follows: given an edge-weighted graph G = (V, E) find a subset
S C V of size at most K such that each vertex in V is "close" to some vertex in
S. More formally, the objective function is defined as follows:

rain m a x m i n
S C V u E V v6S
d(u, v)
where d is the distance function. For example, one may wish to install K fire
stations and minimize the m a x i m u m distance (response time) from a location to
its closest fire station. T h e problem is known to be NP-hard [8].
An approximation algorithm with a factor of p, for a minimization problem,
is a polynomial time algorithm that guarantees a solution with cost at most p
times the optimal solution. Approximation algorithms for the basic K-center
problem have been very well studied and are known to be optimal [7, 9, 10, 11].
These schemes present natural methods for obtaining an approximation factor of
2. Several approximation algorithms are known for interesting generalizations of
* Research supported by NSF Research Initiation Award CCR-9307462, and NSF CA-
REEK Award CCR-9501355. Email addr: -~alair@cs.umd.edu
** Research supported by NSF CAREER Award CCR-9501355. Email addr:
yoram~cs .umd.edu
 153

the basic K-center problem as well [3, 10, 16]. The generalizations include cases
when each node has an associated "cost" for placing a center on it, and rather
than limiting the number of centers, we have a limited budget [10, 16]. Other
generalizations include cases where the vertices have weights and we consider
the weighted distance from a node to its closest center [3, 16].
Recently, a very interesting generalization that we call the capacitated K-
center problem was studied by Bar-Ilan, Kortsarz and Peleg [1]. The input spec-
ifies an upper bound on the number of centers K, as well as a m a x i m u m load
L. We have to output a set of at most K centers, as well as an assignment of
vertices to centers. No more than L vertices m a y be assigned to a single center.
Under these constraints we wish to minimize the m a x i m u m distance between a
vertex u and its assigned center r

min maxd(u, r
SC_VuEV
such that
I{u Ir = v}l < t W S
where
r

Bar-Ilan, Kortsarz and Peleg [1] gave the first polynomial time approxima-
tion algorithm for this problem with an approximation factor of 10. Various
applications for capacitated centers were first mentioned in [14, 15]. A slightly
different problem, where the radius is fixed, and one has to minimize the number
of centers, shows up in the Sloan digital sky survey project [13].

1.1 Our Results

In Section 2 we discuss a simplification of the problem where a node may appear

multiple times in S (i.e. more than one center can be put at a node). We will
refer to this problem as the capacitated multi-K-center problem. By introducing
some new ideas and using the basic approach proposed in [1], we are able to
give a polynomial time algorithm that achieves an approximation factor of 5.
In Section 3 we show how to solve the problem when we are allowed only one
center at a vertex. The high level structure of the algorithm is the same, but
the assignment of centers to vertices has to be done extremely carefully. This
problem will be referred to as the capacitated K-center problem. For this version
of the problem we obtain an approximation factor of 6. It is worth noting that
in fact we prove that our solution is at most 6 times an optimal solution that
is allowed to put multiple centers at a single vertex. This clearly indicates that
there is room for further improvement, since a better lower bound on the optimal
should be possible when at most one center m a y be placed at a vertex.
The algorithm can be easily extended to the more general case when each
vertex has a demand di, and multiple centers may be used to satisfy its demand.
 154

The total demand assigned to any center should not exceed L. Using the method
in [1], we can obtain an approximation factor of 13 for the version with costs.
(Each vertex has a cost for placing a center on it, and we are working with a
fixed budget.) In Section 4 we study some other variants of this problem.

2 Algorithm for Capacitated Multi-K-Centers

We first give a high-level description of the algorithm. We may assume for sim-
plicity that G is a complete graph, where the edge weights satisfy the triangle
inequality. (We can always replace any edge by the shortest path between the
corresponding pair of vertices.)

High-Level Description

The algorithm uses the threshold method introduced by Edmonds and Fulk-
erson in [4] and used for the K-center problem by Hochbaum and Shmoys [9, 10].
Sort all edge weights in non-decreasing order. Let the (sorted) list of edges be
el, e2,...em. For each i, let the threshold graph Gi be the subgraph obtained
from G by including edges of weight at most w(ei). Run the algorithm below for
each i from 1 to m, until a solution is obtained. (Hochbaum and Shmoys [10]
suggest using binary search to speed up the computation. If running time is not
a factor, however, it does appear that to get the best solution (in practice) we
should run the algorithm for all i, and take the best solution.) In each iteration,
we work with the subgraph Gi and view it as an unweighted graph. Since Gi is
an unweighted graph, when we refer to the distance between two nodes, we refer
to the number of edges on a shortest path between them. In iteration i, we find
a solution using some number of centers. If the number of centers exceeds K, we
prove that there is no solution with cost at most w(e~). If the number of centers
is at most K, we show that the maximum distance in Gi between a vertex and
its assigned center is at most five. This gives an approximation factor of 5.
First find a maximal independent set I in G~. (G~ is the graph obtained by
adding edges to Gi between nodes that have a common neighbor.) This technique
was introduced by Hochbaum and Shmoys [9, 10] and has been used extensively
to solve K-center problems. We refer to a node in the maximal independent set
as a monarch. The algorithm also constructs a "tree" of monarchs which will
be used to assign vertices to centers. There are two key differences between our
algorithm and the one presented in [1]:

1. We use a specific procedure to find a maximal independent set, as opposed

to selecting an arbitrary maximal independent set.
2. We deal with all monarchs uniformly rather than dealing with the light and
heavy 3 monarchs separately as in [1].
3 These terms will be explained shortly.
 155

Each monarch has an empire that consists of a subset of vertices within the
immediate neighborhood of the monarch in G~. When a monarch is added to
the maximal independent set, all such vertices that do not currently belong to
an empire are added to this monarch's empire. The algorithm also constructs
a tree of monarchs as the monarchs are selected. This tree has the property
that an edge in the tree corresponds to two monarchs whose distance in Ci
is exactly three. Each monarch then tries to collect a domain of size L - - a
subset of vertices that are close to the monarch and assigned to it. In doing so,
a monarch may grab vertices from other empires if none are available in its own
empire. After this process is complete there may still be unassigned vertices. We
then use the tree of monarchs to assign new centers to handle the unassigned
vertices. Nodes that are left unassigned in a particular empire may be assigned
to the parent monarch. Eventually, we will put additional centers at the monarch
vertices (recall that more than one center may be located at a single vertex).

CAPACITATED-CENTER.S ( e -- (V~ E), K, L).

1 Sort all edges in non-decreasing weight order ( e l , . . . , e r n ) .
2 fori=ltomdo
3 Let Gi = (V, Ei) where Ei - { e l , . . . , ei}.
4 Unmark all vertices.
5 if ASSIGNCENTERS(G/) then exit.
6 end-proc

ASSIONCENTERS (Gi).
1 SUCCESSFUL---- t r u e
2 Let n i be the number of vertices in connected component G i.
9 r
3 xf ()-]r [ n_i_z ]) > K t h e n SUCCESSFUL ---- false
else
4 for each connected component G~ of Gi d o
5 ASSIGNMONARCHS(G~).
6 ASSIGNDOMAINS(G~).
7 REASSmN(G~).
8 i f total centers used > K t h e n SUCCESSFUL ---- false
9 r e t u r n (SUCCESSFUL)
lO e n d - p r o c

ASSIGNCENTERS (Gi) tries to assign centers within each connected compo-

nent. Each component is dealt with separately. (This can be done because if
there is an optimal solution with maximum radius w(ei), then no center in the
optimal solution will be assigned vertices that belong to different connected com-
ponents of Gi.) A lower bound on the number of centers in each component is
r _q.
Lc],
. where nc is the number of vertices in G i.
c If the number of allowed centers
is smaller than )-~c r~-~] then there is no solution.
ASSIGNMONARCI-IS(G~) assigns monarchs (nodes in the independent set) in a
BFS manner. After we put a vertex in the independent set, we mark all unmarked
 156

nodes within distance two in Gi. To pick a new vertex to add to the independent
set, we pick an unmarked vertex that is adjacent to a marked vertex. Rather than
describing the algorithm in terms of (G~) ~ we work with G~, to separate the
nodes in a monarch's empire into level-1 and level-2 nodes. The level-1 nodes
are adjacent to the monarch, and the level-2 nodes are at distance two from
the monarch. We define El(v) and E2(v) to be the level-1 and level-2 nodes,
respectively, in v's empire. Thus the empire of v is El(v) U E2(v).

ASSIQNMONARCHS(G~).
1 Pick an arbitrary vertex v E G~ and set Q = {v}.
2 p(v) = n i l .
3 w h i l e Q has unmarked nodes do
4 Remove an unmarked node v from Q.
5 Make v a monarch and mark it.
6 f o r all u E Adj(v) do
7 if u is unmarked t h e n
8 Add u to El(v) and mark u
9 for all u E Adj(v) do
10 for all w E Adj(u) do
11 if w is unmarked t h e n
12 Add w to E2(v) and mark w
13 f o r all u E E:(v) do
14 for all w E Adj(u) do
15 if w is unmarked a n d w ~ Q t h e n
16 Set p(w) = v and add w to Q
17 e n d - p r o c

Before discussing the pertinent properties of ASSIQNMONARCHS, we show

its execution on the simple example given in Fig. 1. The algorithm starts from
vertex 1, which is made a monarch. Vertex 2 is added to E l ( l ) (level 1 in its
empire) and vertices 3 and 4 are added to E2(1). Q currently contains vertices 51
8 and 10. Vertex 5 is then chosen as a monarch and vertices 6 and 7 are added to
E1(5). Vertices 8 and 9 are both added to E2(5). Q now contains vertices 8, 10,
14 and 16. The next vertex chosen from Q is 10 since 8 is marked. Vertices 11
and 12 are added to El(10), and vertex 13 is added to E2(10). Q now contains
vertices 8, 14 and 16. Vertex 14 is now chosen from Q, and vertices 15 and 16
are added to E1(14) and E2(14), respectively. The algorithm stops since there
are no more unmarked vertices in Q.
There are a few important properties of the monarchs produced by algorithm
ASSIGNMONARCHS.
Important Properties:

1. The distance between any two monarchs is at least three.

2. The distance between a monarch m (except for the root) and its "parent
monarch" p(rn) in the tree is exactly three.
 157

3. The distance between a monarch and any vertex in its empire is at most
two.
4. Each monarch (except for the root) has at least one edge to a level two
vertex in its parent monarch's empire. Moreover, each such level two vertex
has only one such neighbor that is a monarch. More generally, any vertex
can have at most one neighbor that is a monarch (Corollary of property 1).

Procedure ASSIGNDOMAINS tries to assign a domain of size at most L to each

monarch. The objective is to assign as many vertices to a domain as possible
subject to the following constraints.

1. A vertex may be assigned to a monarch's domain only if it is at distance at

most two from the monarch.
2. A monarch may include in its domain a vertex from another empire only if
each vertex in its empire belongs to some domain.

One way to implement this procedure is by finding a min cost maximum flow
in an appropriate bipartite graph. The flow problem has a very simple structure
and there are only two types of costs on edges (0 and 1).

ASSIGNDOMAINS(G$).
1 Let M be the set of monarchs in G~.
2 Let E ' = {(m, v) I m E M, v E V, distance from m to v is at most two }.
3 Construct a bipartite graph G ~ -- (M, V, E').
4 Add vertices s and t. Add edges {(s, m) I m E M } and {(v, t) [ v E Y}.
5 For m E M, v E V, set capacities u(s, m) = L, u(m, v) = 1 and u(v,t) -- 1.
6 Cost of edge e(m, v) -- 1 if v is not in m's empire.
Cost of all other edges is 0.
7 Compute a min-cost m a x i m u m integral flow in G ~.
8 For each monarch rn, set
domain(m) = {v I v receives one unit of flow from m in G'}.
9 For each v, if v E domain(m) then define r = m.
10 e n d - p r o c

D e f i n i t i o n 1. A light monarch is one that has a domain of size < L. A heavy

monarch is one that has unassigned vertices in its empire. A full monarch is one
that is neither heavy nor light.

L e m m a 2 . I f m is a heavy monarch then each vertex in m's domain belongs lo

m's empire.

Proof. Assume that there is a vertex u in m's domain that is not in m's empire.
Let x be a vertex in m's empire that is not assigned to any domain. We can
change the flow function in G ~ and send one unit of flow from m to x instead of
m to u. This produces a m a x flow in G ~ of lower cost, a contradiction, rq
 158

If there is no heavy monarch, all vertices belong to a domain and the algo-
rithm halts successfully.
Let KL be the number of light monarchs. Let nL be the number of vertices
belonging to the domains of light monarchs, and let n be the total number of
vertices.

Theorem3. The number of centers required is at least KL + r(n - nL)/L].

T h e proof is simpler than the proof given in [1]. The following lemmas were
established in [1]. We repeat them for completeness.
Let s be the set of monarchs as defined in [1]. We repeat the definition here.
Let G0 be the set of light monarchs. Iteratively, add to G0 any monarch t h a t
contains a vertex in its domain that could have been assigned to a monarch in
G0.

Gs = G~-I u {rn ~ Ml~v ~ V, 3m I ~ GS_I, r = m and d(v, m 1) _< 2 in Gi}

Let G be the largest set Gj obtained in this process. Let ~v be the set of
remaining monarchs.

Lemma4. The set s does not contain any heavy monarchs.

Proof. Suppose heavy monarch 0 was added .at iteration j. We can transfer a
node v to a center 01 in Gj-1. By a sequence of such transfers, we eventually reach
a center in G0 which has at most L - 1 nodes in its domain, and can absorb the
extra node. This corresponds to a higher flow, since the heavy monarch cab
absorb an unassigned node, a contradiction. []

L e m m a 5 . Consider a center in an optimal solution that covers a monarch in

g. This center cannot be assigned any nodes that are not in the domains of
monarchs in s

Proof. Assume for contradiction that 8 is a center in the optimal solution that
covers b o t h e E E and u. If u does not belong to any domain, then since the
distance from u to e in Gi is at most two, we can perform a sequence of transfers,
eventually reaching a center in s which has at most L - 1 nodes in its domain,
and can absorb the extra node, resulting in a higher flow, a contradiction. If u
belongs to the domain of monarch f , then since the distance from e to u in Gi
is at most two, and the distance from u to f in Gi is at most two, it must be
the case that f E E as required by the lemma. El
 159

Proof. (Of Theorem 3) Each monarch in s is covered by a distinct center in

the optimal solution, and these centers of the optimal solution cannot cover
any other nodes in ~ . Let ne be the number of vertices in the domains of
monarchs in E. Then we need at least ]E I + f! ( n -Ln ~ ]1 centers. This is the same as
KL + [('~+(leI-KL)'L-ne )1" Since ne = ( ] E l - KL). L + nL we get KL + [ ( m ~ ) ] .
O

We will prove that this is also an upper bound on the number of centers we
USe,

REAssmN(G~).
1 Let M be the set of monarchs in G~.
2 For each monarch m E M, set
unassigned(m) = ({m} U El(m) U E2(m)) \ (UueMdomain(u)).
3 Let T be the tree of monarchs in G~.
4 f o r all nodes m in T, set passed(m) = 0.
5 w h i l e T is not empty d o
6 Remove a leaf node m from T.
7 Let lunassigned(m)l + ]passed(m)[ = k'L + e
8 Allocate k' new centers at monarch m and assign k'L of the nodes
to them. For each such node v we define r =- m.
9 Assign the e remaining nodes to monarch m and for each such
node v define r = m, freeing UP to e nodes in domain(m).
10 Add the freed nodes to passed(p(m)).
11 Delete m from T.
12 e n d - p r o e

T h e o r e m 6. Each vertex is assigned to a center whose distance in Gi is at most

5. Moreover, we use at most KL + [(n -- nL)/L] centers.

Proof. All centers except possibly light monarchs cover L nodes by construction.
The size of the domain of a light monarch does not decrease. Therefore the total
number of centers used is at most KL + [(n - nL)/n].
A node is either covered by the node from which it receives flow, or by the
parent of its original monarch. In the former case, it is at distance at most two
from the center that covers it. In the latter case the passed nodes are always
covered by their monarch's parent, i.e., they are only passed once. Thus the
distance from a node to the center that covers it is at most five (at most two to
its original monarch, and three more to the parent monarch). U

3 Algorithm for/C-Centers

We now consider the version where we are required to pick K distinct vertices as
centers. We use the same high level approach as in the previous case, but need
 160

to pick the centers carefully. We are able to show that the algorithm obtains an
approximation factor of 6. (Obtaining a factor of 7 using the previous approach
is easy.)
The main difficulty lies in allocating centers to cover the vertices left unas-
signed by ASSmNDOMAINS. We first introduce some new notation.
Nodes in a monarch's empire are called its subjects. In ASSIGNMONARCHS,
each level-2 subject w of a monarch is brought in by a node u at distance 1
from the monarch. We define link(w) = u. Each monarch m (except the root)
was placed into Q by a unique level-2 subject of its parent monarch. This node
is called the spouse s(m) of monarch m (Fig. 1). Note that each monarch has
a unique spouse, and a node can be the spouse of at most one monarch (by
property 4).
We need to be careful when allocating new centers to cover unassigned nodes.
We require that: (1) a node can only be allocated as a center once; (2) monarchs
have sufficient available nodes to allocate centers for the nodes passed to them.
To ensure this we enforce the following rule. A monarch m a y allocate centers of
the following types only:

1. Nodes in its empire, or

2. Nodes at distance 1 from itself (which m a y not be in its empire), as long as
a monarch does not allocate its spouse as a center.

We define a tree T(m) of height 2 corresponding to each monarch m. The

root of T(m) is monarch m. The leaves of this tree are all the level-2 subjects of
m that are the spouse of some other monarch. For any leaf w, we make link(w)
the parent of the leaf. These nodes are the children of m in the tree T(m).
In Fig. 2 we show a monarch m together with all the level-2 subjects of m
that are the spouse of some other monarch (for example ml). For each leaf w,
we also show link(w). Notice that link(w) m a y not be in monarch m's empire.
Observe that nodes that are the spouse of some monarch may belong to two
trees. We therefore specify that a monarch m a y assign a center to any vertex in
its tree T(m) other than its spouse. This ensures that no vertex is assigned as
two centers by two different monarchs.
Tree T(m) will be used in assigning vertices that are passed to monarch m.
Nodes passed from monarch m t to monarch m are covered by one of five nodes:
The spouse of monarch m', i.e., s(m'), the spouse's link iink(s(m')), the spouse of
a sibling monarch s(n) (where p(n) -- p(m') = m and link(s(n)) = link(s(ml))),
the link of a sibling monarch's spouse iink(s(n)) (where p(n) -- p(m') = m), or
monarch m.
A monarch does not allocate centers at nodes that are passed to it. Because
of this, we may have to allocate centers at vertices that are already assigned to
a center. We therefore specify that in this case the new center does not cover
 161

itself, but covers L other vertices. A vertex allocated as a center which is not
assigned to a center covers itself as well as L - 1 other vertices.

T h e algorithm given in this section differs from t h a t in Section 2 in the se-

lection of new centers to cover the vertices left unassigned by ASSIGNDOMAINS.
We first give a high-level description of the new selection scheme and then a new
REASSIGN procedure t h a t implements the scheme.

High-Level Description

We repeatedly .select a leaf monarch in the tree of monarchs and allocate

centers to cover nodes in its empire as well as nodes passed to it from its children
monarchs. Let m be the monarch currently under consideration. If rn p is a child
m o n a r c h of m, we will assume t h a t m p passes the excess nodes in its empire to
m. Each leaf node s(m') in T(m) is labelled with the number of excess nodes
t h a t monarch m ~ is passing to m.

Nodes passed to m are assigned to centers placed on nodes in T(m). There

are a few i m p o r t a n t things to note here. (1) When we begin to process m o n a r c h
m, no centers are currently placed at any nodes in T(m) (except for m itself).
(2) Monarch m is responsible for allocating centers for all the nodes t h a t are
passed to it from its children monarchs. (3) Monarch m is responsible for the
free nodes in its empire. However, some of the free nodes at distance 2 from rn
m a y belong to trees of other monarchs, and m a y have centers already placed on
t h e m , in which case we will assume they are assigned to their own centers. I f a
vertex at distance 2 is in monarch m ' s domain, and a center is placed on it by
the tree it belongs to, then it remains in m ' s domain and does not change its
assignment.

Monarch m first assigns the nodes that are passed to it from children m o n a r -
chs, using T(m) to place full centers. Any nodes that are left over (at m~st L - 1),
t h a t were not assigned, are assigned to monarch m, displacing vertices that were
in m ' s domain, which become unassigned. At this stage there m a y be m a n y free
nodes in m ' s empire - nodes that were never part of a domain, as well as the
nodes t h a t were recently displaced from m ' s domain. Note that the nodes t h a t
were never p a r t of a domain do not have a center on them, while the ones t h a t
were displaced from m ' s domain could have centers placed on them (since they
m a y belong to other trees and m a y have been chosen as centers). However, there
are at most L - 1 of these, so any which do not get assigned within m ' s empire
can be passed to m ' s parent monarch. We now choose centers from the set of
nodes t h a t never belonged to any domain. In doing so, we m a y assign some of
the displaced nodes as well. T h e remaining unassigned vertices, including the
displaced nodes, are passed to m ' s parent monarch.

We now describe in detail how the passed vertices are handled. Group the
leaves of T(m), placing leaves u and v in the same group iff link(u) = link(v).
 162

We process the groups in turn, processing the group whose c o m m o n link is s(m)
last, if such a group exists.
We assign passed nodes to centers by processing the groups in order. We
process a leaf node in a group as follows: We start by adding the vertices passed
to the leaf node to a list called pending. Whenever pending has at least L
vertices, we create a center and assign vertices to it. There are two things we
have to be careful about - if we create a center at a vertex that is free, we have
to assign the vertex to its own center. If a center is going to be assigned vertices
f r o m different groups we move the center up one level, from a leaf node to the
link node. Centers chosen in the last group are not assigned any vertices from
other groups, and so we never assign a center at s(m), but only at leaf nodes in
this group.
To ensure t h a t nodes in T(m) do not have centers placed on them, we process
the monarchs in T in the reverse of the order in which they were placed in T.
Note t h a t if a node v in T(m) belongs to the empire of another monarch m ~,
then m ~ m u s t have been placed in T before m, otherwise m would have placed v
in its own empire. We thus process m before m ~. If a center is placed at v by m
then v is assigned to itself in case it was free. When we eventually process m ~,
we are guaranteed that if v is free, it does not have a center placed on it.
For the last group, we proceed as above, except t h a t any nodes carried over
f r o m the last group are picked up by monarch m, possibly replacing some nodes
already assigned to m. These replaced nodes are either passed or allocated a
center in El(m)U E2(m) by monarch m. (Note t h a t if monarch m is light, then
the nodes are passed, if not then it does not grab nodes from other empires, so
it is safe to allocate centers a t / f o r them).
T h e proof is too long to include here but will be provided in the full paper.

Example
Before describing the pseudo-code, we discuss the example given in Fig. 3
in detail. We process the leaves from left to right. Each leaf is labeled with the
n u m b e r of vertices that are passed to it from the corresponding child monarch.
Assume t h a t L is 10. After we process ul, pending(m) has size 4, and no centers
are allocated. When we process u~, pending has size 12. Since we can allocate
a full center at u2, we do so. Since u2 is free, we assign us to itself and assign
9 (-- L - 1) vertices from pending(m) to us. T h e size of pending(m) is now 3.
In processing u3, we add 2 more vertices to pending(m). Before we process the
leaves in v2's group, we set X = vl. Observe that vertices passed to nodes in v l ' s
group are going to share a center with vertices passed to nodes in v2's group,
hence we "promote" the center one level up. When we process u4 and us, we
add 3 more vertices to pending(m) t h a t now has size 8. We then process u6,
adding 8 vertices to pending(m). Since we can allocate a full center, we allocate
a center at vl (current value of X ) . Since vl is currently unassigned, we assign
vl to itself and assign 9 ( = L - 1) vertices from pending(m) to it. T h e size of
 163

pending(m) is now 7. When we process uz, we add 5 vertices to pending. Since

we can allocate a full center, we create a center at u7. Since u7 is assigned, we
assign 10 vertices from pending(m) to it. This leaves 2 vertices in pending(m)
that are assigned to monarch rn, possibly displacing other assigned vertices.

REAsslCN(G~).
1 Let M be the set of monarchs in G~.
2 For each monarch m E M , set
unassigned(m) = ({m} U El(m) U E~(m)) \ (U~Mdomain(u)).
3 For each monarch m E M, let pending(m) be an ordered list, initially 0.
4 Let T be the tree of monarchs in G~.
5 f o r all nodes m in T d o
6 Define T(m) such that the group containing s(m) comes last.
7 f o r all leaf nodes v in T(m)) d o set passed(v) = 0.
8 f o r all nodes v in G~, let X(v) = {v} iff v is unassigned and 1~ otherwise.
9 f o r all nodes m in T, process them in reverse order of their insertion into T:
10 Set X = null.
11 f o r all children v of m in T(m) d o
12 f o r all children u of v in T(rn) d o
13 Append passed(u) to pending(m).
14 i f X = n u l l t h e n set X = u.
15 i f Ix(X)I + ]pending(m)] >_L then
16 Allocate a center at X and assign x(X) to it.
17 Assign the first L - Ix(S)l nodes from pending(m) to X and
remove them from pending(m).
18 Set X = null.
19 else i f X = u t h e n set X = null.
20 i f v ~ s(m) a n d X = n u l l t h e n
21 i f IX(v)[ + Ipending(m)[ = Z t h e n
22 Allocate a center at v and assign X(V) to it.
23 Remove all nodes from pending(m) and assign them s v.
24 else set X = v.
25 Let displaced(m) = Idomain(m)l + Ipending(m)l _ L.
26 Assign all nodes in pending(m) to m,
possibly displacing nodes in domain(m).
27 Let lunassigned(m)] + displaced(m) = k'L + e.
28 Allocate k I new centers at nodes in unassigned(m).
29 Assign k'L of the nodes to them, assigning nodes in unassigned(m) first.
30 Add the e remaining nodes to passed(s(m)).
31 Delete m from T.
32 e n d - p r o c

3.1 Capacltated C e n t e r s w i t h C o s t s

The capacitated K-center problem with costs is a generalization of the capaci-

tated K-center problem where a cost function is defined on the vertices and the
 164

objective is to pick a set of centers whose total cost is at most K, such that the
radius is minimized. (Note that this is equivalent to the weighted capacitated
K-center problem in [1]. We use cosl here to distinguish from weights as defined
in, for example, [3, 16].) More formally, we are given a cost function c : V --* 7r +,
and we add the constraint ~ s c(v) < K to the statement of the capacitated
K-center problem.
Bar-Ilan, Kortsarz and Peleg gave the first polynomial time approximation
algorithm for this problem with an approximation factor of 21. Their technique,
which involves finding a minimum-cost perfect matching in a bipartite graph,
generalizes to finding a 2p + 1 solution given a p-approximation algorithm for
the capacitated K-centers problem. It therefore yields an approximation algo-
rithm with an approximation factor of 13 when combined with our algorithm for
capacitated K-centers.

4 Remarks

It is possible to improve the quality of the approximation if one is willing to

allow some slack on the number of centers used and the maximum load. Let
a (clK, c2L, c3R) solution denote a solution using at most czK centers, each
with a load of at most c~L, which assigns every node to a center at distance
at most c3R, where R is the radius of the optimal solution. For the capacitated
multi-K-center problem, we can obtain for any integer x >_ 1 a (~K, cn, 2R)
solution, where c = ~ , by overloading centers by up to L, and allocating
extra centers for more than ~ unassigned nodes. For the capacitated K-center
problem, the same approach gives a (~K, cL, 4R) solution. Results of Lund and
Yannakakis [12] and Feige [6] imply that no polynomial time (ctg, c2L, ( 2 - ~)R)
approximation algorithm is possible unless N P C DTIME(n~176176 since
this would imply a constant-factor approximation algorithm for set cover.
A c k n o w l e d g e m e n t s : We thank Robert Pless and Balaji Raghavachari for use-
ful discussions, and the referee for helpful comments.

References
1. 3. Bar-Ilan, G. Kortsarz and D. Peleg, "How to allocate network centers", 1. Al-
gorithms, 15:385-415, (1993).
2. T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms, The MIT
Press, 1989.
3. M. Dyer and A. M. Frieze, "A simple heuristic for the p-center problem", Opera-
tions Research Letters, Vol 3:285-288, (1985).
4. J. Edmonds and D. R. Fulkerson, ~Bottleneck extrema', Journal of Combinatorial
Theory, Vol 8:299-306, (1970).
5. T. Feder and D. Greene, "Optimal algorithms for approximate clustering", Proc.
of the 20 th ACM Symposium on the Theory o] Computing, pages 434-444, (1988).
 165

6. U. Feige, "A threshold of In n for approximating set cover", Proc. o]the 28 th ACM
Symposium on the Theory of Computing, pages 314-318, (1996).
7. T. Gonzalez, "Clustering to minimize the maximum inter-cluster distance", The-
oretical Computer Science, Vol 38:293-306, (1985).
8. M. R. Gaxey and D. S. Johnson, "Computers and Intractability: A guide to the
theory of NP-completeness", Freeman, San Francisco (1978).
9. D. Hochbaum and D. B. Shmoys, "A best possible heuristic for the k-center prob-
lem", Mathematics of Operations Research, Vol 10:180-184, (1985).
10. D. Hochbaum and D. B. Shmoys, "A unified approach to approximation algo-
rithms for bottleneck problems", Journal of the ACM, Vol 33(3):533-550, (1986).
11. W. L. Hsu and G. L. Nemhauser, "Easy and hard bottleneck location problems",
Discrete Applied Mathematics, Vol 1:209-216, (1979).
12. O. Lund and M. Yannakakis, "On the hardness of approximating minimization
problems", Journal o] the ACM, Vol 41(5):960-981, (1994).
13. R. Lupton, F. M. Maley, and N. E. Young, "Data collection for the Sloan digi-
tal sky survey - a network-flow heuristic", Proc. of the 7 th Annual ACM-SIAM
Symposium on Discrete Algorithms, pages 296-303, (1996).
14. H. L. Morgan and K. D. Levin, "Optimal program and data locations in computer
networks", Communications of the ACM, Vol 20:315-322, (1977).
15. K. Murthy and g. Kam, "An approximation algorithm to the file allocation prob-
lem in computer networks", Proc. of 2 "d ACM Symposium on Principles of
Database Systems, pages 258-266, (1983).
16. 3. Plesnik, "A heuristic for the p-center problem in graphs", Discrete Applied
Mathematics, Vol 17:263-268, (t987)
17. C. Toregas, R. Swain, C. Revelle and L. Bergman, =The location of emergency
service facilities", Operations Research, Vol 19:1363-1373, (1971).

r" . . . . . . . . . . .

, 1 ]
I I
I I

80o)=3 l~ 1 "i-Ir---llc I ,(5)=4

/1;
tink(13) = I113' ' link(s)

IN I ,~14; '(14)----9

.... >_%- li-k(16) = 8

a,'

Fig. 1. Example to illustrate finks and spouses.

 166

F . . . . . . . . . . -I F . . . . . . . . . . .
I I
I I
I I
I I

link(s(mq~ i t
_ _ _" " _ "_'_ _ _ J L ~ __-~ ~_(2)~
~ .......... n . . . . . 7 Monarch rn's empire
l I x,',. /
I I I I

,
......~ ,(~') z I j l_}_,,
I L L ~~_
_.~ :
. . . .
, . , , . , . ,
I t I I I l I I
i~/~ n I I I I I I
I I I I I I I
I I I I I I I
I I I I I I I
I I I I I I I
I I I I I I I
I I I I I I I
L---.J L----J L---2 L--.J L---J L__2 L___I L___I L__-I L__-I

F i g . 2. E x a m p l e to illustrate tree T ( m ) of a monarch m .

L=10
(E) = unassigned vertex

~-] =centers
~1 U2 ~3 U4 ?/,5 ~6 ?t,7

4 8 2 1 2 8 5

Fig. 3. Ex&mple to illustrate assignment of centers in tree T(m).