Approximating Connected Facility Location Problems via
Random Facility Sampling and Core Detouring
Friedrich Eisenbrand∗Fabrizio Grandoni†Thomas Rothvo߇Guido Sch¨afer§
July 6, 2007
Abstract
We present a simple randomized algorithmic framework for connected facility location problems. The
basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility loca-
tion problem, randomly sample the clients, and open the facilities serving sampled clients in the approx-
imate solution. Via a novel analytical tool, which we term core detouring, we show that this approach
significantly improves over the previously best known approximation ratios for several NP-hard network
design problems. For example, we reduce the approximation ratio for the connected facility location
problem from 8.55 to 4.00, and for the single-sink rent-or-buy problem from 3.55 to 2.92. We show
that our connected facility location algorithms can be derandomized at the expense of a slightly worse
approximation ratio. The versatility of our framework is demonstrated by devising improved approxi-
mation algorithms also for other related problems.
∗Institut f¨ur Mathematik, Universit¨at Paderborn, Germany. Email: [email protected]orn.de.
†Dipartimento di Informatica, Universit`a di Roma “La Sapienza”, Via Salaria 113, 00198 Roma, Italy. Email:
‡Institut f¨ur Mathematik, Universit¨at Paderborn, Germany. Email: rothvo[email protected]orn.de.
§Technische Universit¨at Berlin, Institut f¨ur Mathematik, Straße des 17. Juni 136, 10623 Berlin, Germany. Email:
1 Introduction
We consider network design problems that combine facility location and connectivity problems. These
problems have a wide range of applications and have recently received considerable attention both in the
theoretical computer science literature (see, e.g., [9, 12, 17, 26]) and in the operations research literature
(see, e.g., [19, 23]).
As an example (see also [1, 26]), consider the problem of installing a telecommunication network in-
frastructure. The network consists of a central high-bandwidth core with unlimited capacity on the links and
individual connections from endnodes to nodes in the core. Among the potential core nodes, we need to
select a subset that we connect with each other, and then route the traffic from each endnode to a core node.
Each core node comes with an installation cost and we assume that the cost of installing the high-bandwidth
links in the core is larger than the (per unit) routing cost from the endnodes to the core.
We can model the scenario above as a connected facility location problem (
CFL
). We are given an
undirected graph G= (V,E)with edge costs c:E→Q+, a set of facilities F⊆V, a set of clients D⊆V,
and a parameter M≥1. Every facility i∈Fhas an opening cost f(i)∈Q+and every client j∈Dhas
a demand d(j)∈Q+. The goal is to determine a subset F⊆Fof the facilities to be opened, assign each
client j∈Dto some open facility σ(j)∈Fand to build a Steiner tree Tconnecting the open facilities such
as to minimize the total cost
∑
i∈Ff(i) + M∑
e∈Tc(e) + ∑
j∈D
d(j)ℓ(j,σ(j)),(1)
where ℓ(v,w)is the shortest path distance between vertices v,w∈Vin G(with respect to c). We refer to
the first, second and last term in (1) as the opening cost,Steiner cost and connection cost, respectively.
Subsequently, we assume that every client j∈Dhas a unit demand d(j) = 1. This assumption is without
loss of generality as we may replace jby several copies of co-located unit-demand clients. The algorithms
presented in this paper can easily be adapted in order to run in polynomial time even if the original demands
are not polynomially bounded in the number nof vertices; we refer the reader to [12] for additional details.
The special case where F=Vand all opening costs are zero is known as the single-sink rent-or-buy
problem (
SROB
). There are various natural extensions of
CFL
that differ with respect to the underlying
facility location and core connectivity problem. For example, in the connected k-facility location problem
(
k-CFL
) we can open at most kfacilities. We may alternatively consider the variant of
CFL
where the open
facilities are connected by a traveling salesman tour. We call the latter problem the tour-connected facility
location problem (
tour-CFL
).
Our Results. We present an algorithmic framework to devise simple approximation algorithms for con-
nected facility location problems. Via a novel analytical tool, which we term core detouring, we are able to
show that this framework yields approximation algorithms that significantly improve over the previous best
approximation ratios for the problems mentioned above. From a high level point of view, our framework
works as follows:
1. Compute an approximate solution for the (unconnected) facility location problem.
2. Randomly sample the clients and open the facilities serving sampled clients in the approximate solu-
tion.
3. Compute an approximate solution for the connectivity problem on the open facilities and assign clients
to the open facilities.
We remark that in Steps 1 and 3, we can use any approximation algorithm for the (unconnected) facility
location and core connectivity problem as a black box—this allows us to use the current best approximation
algorithms for the respective subproblems.
1
Problem This paper Previous best
CFL
4.00∗8.55 Swamy and Kumar [25, 26]
4.23
SROB
2.92∗3.55∗Gupta et al. [11, 12]
3.28 4 van Zuylen and Williamson [27]
k-CFL
6.85∗15.55∗Swamy and Kumar [25, 26]
6.98
tour-CFL
4.12∗5.83∗Ravi and Salman [22] (special case only)
Table 1: Improved approximation ratios obtained in this paper; expected approximation ratios are marked with a star.
Our framework yields a 4.00-approximation algorithm for
CFL
, which improves over the current best
primal-dual 8.55-approximation algorithm by Swamy and Kumar [25, 26]. In the special case of
SROB
,
our algorithm provides a 2.92-approximation, hence improving on the current best 3.55-approximation al-
gorithm by Gupta et al. [10, 11]. We show that our algorithms for
SROB
and
CFL
can be derandomized
using the method of conditional expectations (see, e.g., [20]) and an idea that van Zuylen and Williamson
[27] used to derandomize the
SROB
algorithm of Gupta et al. [10, 11]; thereby the approximation ratios
degrade only slightly. We eventually demonstrate the versatility of our framework by applying it to the
problems
k-CFL
and
tour-CFL
, for which we improve the current best known approximation ratios. The
results presented in this paper are summarized in Table 1.
A key ingredient in our analysis is that we use a novel core detouring scheme to bound the expected
connection cost of random sampling algorithms. The basic idea is to construct (ideally) a sub-optimal
connection scheme and to bound its cost in terms of the optimum cost. In this scheme, we reassign the
clients to open facilities by detouring their connection paths through the core in the optimum solution.
This construction is set up such that the reassignment is perfectly symmetric, which allows us to bound
the expected cost of the detoured paths. As a by-product of our analysis, we obtain a polynomial-time
approximation scheme (PTAS) for the above problems if |D|/Mis a constant. This might be of independent
interest.
Previous and Related Work. The network design problems considered here are NP-hard [8] and APX-
complete [2, 4, 21], as they contain the Steiner tree problem or the metric traveling salesman problem as
a special case. Researchers have therefore concentrated on obtaining good approximation algorithms for
them.
CFL
and
SROB
have recently received considerable attention in the computer science literature. Gupta
et al. [9] obtain a 10.66-approximation algorithm for
CFL
, based on rounding an exponential size LP.
The current best algorithm for
CFL
is a primal-dual 8.55-approximation algorithm by Swamy and Ku-
mar [25, 26]. Better results are known for
SROB
. Gupta et al. [9] give a 9.01-approximation algorithm.
Swamy and Kumar [25, 26] describe a primal-dual 4.55-approximation algorithm for the same problem.
Gupta, Kumar, and Roughgarden [12] propose a simple random sampling algorithm which gives a 3.55-
approximation. Gupta, Srinivasan and Tardos [14] show that this algorithm can be derandomized to obtain a
4.2-approximation algorithm. In a recent work, van Zuylen and Williamson [27] present a derandomization
of the random sampling algorithm that yields a 4-approximation.
Swamy and Kumar [25, 26] give a 15.55-approximation algorithm for
k-CFL
, which is also the current
best. Ravi and Salman [22] consider the special case of
tour-CFL
, where F=Vand all opening costs are
zero, and give a 5.83-approximation for it.
Most of the existing random sampling algorithms for connected facility location problems are analyzed
2
by means of strict cost shares (see, e.g., [10, 12] and in particular the exposition in [11]), a concept originat-
ing from game-theoretic cost sharing. Basically, these cost shares are used to relate the expected connection
cost of the computed solution to the cost of the core in the optimum solution. This concept has been used
successfully to obtain simple and good approximation algorithms for network design problems, such as
SROB
[11, 12] and
MROB
[3, 7, 10], the multi-commodity counterpart of
SROB
. However, its use failed to
prove better bounds for more general connected facility location problems. In fact, in [12], Gupta et al. leave
open the question whether a randomized sampling approach can be used to improve the primal-dual approx-
imation algorithm of Swamy and Kumar [25, 26]. In this paper, we answer this question affirmatively.
Organization of Paper. In Section 2, we study core connection games, which form the basis of our core
detouring scheme. We present the polynomial-time approximation scheme for constant D/Min Section 3.
Our random facility sampling framework for
CFL
and
SROB
and its analysis are given in Section 4. The
extensions of this framework to other connected facility location problems are outlined in Section 5. Finally,
we give some conclusions in Section 6.
2 Core Connection Games
In this section, we study some random games that we call core connection games. These games form the
basis of our core detouring scheme introduced in Section 4.
Consider the following setting. We are given a set Nof core nodes that are connected by an undirected
cycle C, which we call the core. Every core node i∈Nhas exactly one client node j ∈Dassigned to it, i.e.,
|N|=|D|. We use µ(j)∈Nto refer to the core node of j∈D. Each client node j∈Dhas two oppositely
directed edges (j,i)and (i,j)to its respective core node i=µ(j); see Figure 1 in the Appendix. Let Hin
be the set of all edges that are directed from client nodes to core nodes and Hout the set of all oppositely
directed edges. Define H=Hin ∪Hout. Let G= (V,E)be the resulting graph and w:E→Q+a non-
negative weight function on the edges of G. We slightly abuse notation here by using C⊆Eto refer to the
set of undirected edges in the cycle. By w(S)we denote the total weight of all edges in S⊆E.
We now consider the following random cycle-core connection game: We mark one client node uniformly
at random, and every other client node independently with probability p∈(0,1). Now, every client node
j∈Dsends one unit of (unsplittable) flow to the closest marked client node (with respect to the distances
induced by w). We bound the cost of the total flow sent in this game in the following theorem.
Theorem 1. The cost X of the flow in the cycle-core connection game satisfies E[X]≤w(H)+w(C)/(2p).
Proof. We bound the cost of the following sub-optimal flow routing scheme: Every client j∈Dsends its
flow unit to a closest marked client, with respect to unit edge weights (breaking ties uniformly at random);
see Figure 1. The symmetry properties of this routing scheme make it easier to bound its expected cost.
Let f(e)be the flow on edge e∈Eand let Ydenote the total cost of this flow (with respect to the original
weights). Clearly, E[X]≤E[Y].
By linearity of expectation, the cost of this flow is
E[Y] = ∑
e∈H
E[f(e)]·w(e)+ ∑
e∈C
E[f(e)]·w(e).
Note that f(e)≤1 holds deterministically for every edge e∈Hin. By symmetry reasons, E[f(e)] ≤1 for all
edges e∈Hout.
It remains to bound the expected flow on the edges of the cycle. Again exploiting the symmetry of the
routing scheme, it is sufficient to consider an arbitrary edge e∈C. Let Xjbe the number of edges of the
3
cycle crossed by the flow-path of a given client node j. Clearly,
∑
e∈C
f(e) = ∑
j∈D
Xj.
By symmetry, we can conclude that E[f(e)] = E[Xj]. Let us call a core node i=µ(j)by-sampled if jis
sampled. We now observe that Xj>kif and only if iand the first knodes of Cto the left and right of iare
not by-sampled. As a consequence Pr(Xj>k)<(1−p)2k+1,
where the strict inequality is due to the fact that at least one core node is by-sampled by assumption. We
conclude that
E[f(e)] = E[Xj] = ∑
k≥0
Pr(Xj>k)≤1−p
1−(1−p)2=1−p
p(2−p)≤1
2p.
The theorem follows.
We can modify the cycle-core connection game in a way which is better suited for our purposes. Suppose
the core is given by an (undirected) Steiner tree Ton the core nodes in Ninstead of a cycle. The tree T
may contain some other non-core nodes. As before, every client node j∈Dis assigned to exactly one core
node µ(j). Let µ−1(i)be the set of client nodes assigned to a core node i∈N. However, a core node i∈N
might now have more than one client node assigned to it, i.e., we have |µ−1(i)| ≥ 1 for every i∈N. The
rest of the construction remains the same as before. We define a tree-core connection game analogously to
the cycle-core connection game.
Corollary 1. The cost X of the flow in the tree-core connection game satisfies E[X]≤w(H)+w(T)/p.
Proof. We transform the Steiner tree Tinto a cycle Cusing the following standard arguments: We replace
every edge of the tree by two oppositely directed edges and compute a Eulerian tour on the resulting graph.
Starting from an arbitrary core node in N, we traverse this tour and shortcut all nodes that do not belong to
Nor have been visited before. Let the resulting cycle on the core nodes Nbe C′. By triangle inequality,
w(C′)≤2w(T).
We now replace every core node iin C′by a path of |µ−1(i)|copies of iand assign every client node jin
µ−1(i)to a unique random copy, i.e., compute a random matching between the client nodes and the copies.
The weights of the edges in this replacement path are set to zero. Denote the cycle obtained in this way by
C. We finally add the two oppositely directed edges between every client node jand its unique copy in C.
Let Ybe the cost of the flow in the cycle-core connection game. It is not difficult to see that X≤Yholds
deterministically. The claim now follows from Theorem 1 and the fact that w(C) = w(C′)≤2w(T).
3 Polynomial-time Approximation Schemes for Constant |D|/M
In this section, we present polynomial-time approximation schemes (PTAS) for the connected facility loca-
tion problems considered in this paper if |D|/Mis upper bounded by a constant. These PTAS will help to
improve our analysis for the general case; but might also be of independent interest.
Recall that ℓ(v,w)denotes the shortest path distance between vertices vand win the graph G= (V,E)
with respect to c. We also define ℓ(v,W) = minw∈Wℓ(v,w)for a given subset W⊆V. Let c(S) = ∑e∈Sc(e)
denote the total cost of all edges in a subset S⊆E.
Theorem 2. If |D|/M=O(1), there is a PTAS for
k-CFL
.
4
Proof. Let
OPT
= (F∗,T∗,σ∗)be an optimal solution for
k-CFL
. We use Z∗,O∗,S∗and C∗to refer to
its total, opening, Steiner, and connection cost, respectively. If kis a constant, we can trivially compute
an optimum solution in polynomial time. Let m≥1 be an arbitrary integral constant and assume k≥2m.
Consider the following algorithm:
1. For all possible choices of F⊆Fwith |F| ≤ 2mdo:
(a) Compute an optimal Steiner tree Tover F.
(b) Assign every client j∈Dto its closest facility σ(j)in F.
2. Output a minimum cost solution (F,T,σ)obtained.
In Step 1(a), we use, for example, the algorithm by Dreyfus and Wagner [6]. Note that the algorithm outputs
a feasible solution, since 2m≤k, and runs in polynomial time.
It is sufficient to show that there is a proper choice of Fwhich satisfies the claim. Let us construct F
as follows: Initially, set F:={i∗}, where i∗is an arbitrary facility in F∗. Then, while there exists a facility
i∈F∗with ℓ(i,F)>c(T∗)/m, add ito F. Note that this way, we ensure that the following two properties
hold for the final set F:
1. For any two facilities i,i′∈F,ℓ(i,i′)>c(T∗)/m.
2. For every facility i∈F∗, there is a facility i′in Fsuch that ℓ(i,i′)≤c(T∗)/m.
We first show that |F| ≤ 2m. To see this, double the edges of T∗, compute an Eulerian tour E∗on the
resulting graph, and shortcut the vertices not in F. The cost of the resulting tour on Fis at least |F|·c(T∗)/m
due to Property 1. Moreover, the cost of the Eulerian tour is c(E∗)≤2c(T∗). Thus, |F|·c(T∗)/m≤2c(T∗),
which implies that |F| ≤ 2m.
We next bound the cost Zof the solution
APX
= (F,T,σ)for our particular choice of F. Clearly,
c(T)≤c(T∗), since F⊆F∗and we compute an optimum Steiner tree Tover F. Therefore,
Z=∑
i∈Ff(i)+Mc(T)+ ∑
j∈D
ℓ(j,σ(j)) ≤∑
i∈F∗
f(i)+ Mc(T∗)+ ∑
j∈D
ℓ(j,σ∗(j))+ ∑
j∈D
ℓ(σ∗(j),F)
≤O∗+S∗+C∗+|D|· c(T∗)
m=Z∗+|D|
M·Mc(T∗)
m=Z∗+O(1)·S∗
m≤1+O(1)
mZ∗.
For the second inequality, we exploit the fact that ℓ(σ∗(j),F)≤c(T∗)/mby Property 2. Since we can
choose marbitrarily large, the claim follows.
Corollary 2. If |D|/M=O(1), there is a PTAS for
CFL
.
Using essentially the same arguments as above, it is not hard to obtain a PTAS for
tour-CFL
under the
same assumptions. We state the following theorem without proof.
Theorem 3. If |D|/M=O(1), there is a PTAS for
tour-CFL
.
4 Connected Facility Location
Due to the results obtained in the previous section, we can assume that M/|D| ≤ εfor a sufficiently small
constant ε>0. We also assume without loss of generality that n≫1. For a given assignment σof clients to
facilities, we let σ−1(i)denote the set of clients assigned to facility i.
5
4.1 Random Facility Sampling
Let α∈(0,1]be a constant parameter which will be fixed later. Our algorithm randCFL for
CFL
works as
follows:
1. Compute a ρfl-approximate solution
U
= (F
U
,σ
U
)for the (unconnected) facility location instance
induced by the input instance.
2. Choose a client j∗∈Duniformly at random, and mark it. Mark every other client jindependently
with probability α/M. Let Dbe the set of marked clients.
3. Open facility i∈F
U
if there is at least one marked client in σ−1
U
(i). Let Fbe the (non-empty) set of
open facilities.
4. Compute a ρst-approximate Steiner tree on D. Augment this tree by adding the shortest path between
every j∈Dand the corresponding open facility σ
U
(j)∈F. Extract a tree Tspanning Ffrom the
resulting multi-graph.
5. Output APX = (F,T,σ), where σassigns each client j∈Dto a closest open facility in F.
In Step 4 we might alternatively construct a Steiner tree directly on the open facilities in F; however, this
would lead to a worse approximation factor.
We use the following notation. An optimal solution is denoted by
OPT
= (F∗,T∗,σ∗). We use Z∗,O∗,
S∗and C∗to refer to its total, opening, Steiner, and connection cost, respectively. Similarly, we use Z,O,
Sand Cto refer to the respective costs of
APX
. We let O
U
and C
U
be the opening and connection cost,
respectively, of the approximate solution
U
= (F
U
,σ
U
)for the unconnected instance computed in Step 1.
Lemma 1. The opening cost of
APX
satisfies O ≤O
U
.
Proof. We open a subset of the facilities in F
U
, which costs at most O
U
.
The following bound on the Steiner cost is inspired by [12]. We recall that we assume M/|D| ≤ ε.
Lemma 2. The Steiner cost of
APX
satisfies E[S]≤ρst(S∗+ (α+ε)C∗)+ (α+ε)C
U
.
Proof. We obtain a feasible Steiner tree on the marked clients in Dby augmenting the optimal Steiner tree
T∗by the shortest paths from each client in Dto T∗. This Steiner tree has expected cost at most
∑
e∈T∗
c(e)+ ∑
j∈Dα
M+1
|D|ℓ(j,F∗) = 1
MS∗+α
M+1
|D|C∗.
Thus the expected cost of the ρst-approximate Steiner tree over Dcomputed in Step 4 is at most
ρst
MS∗+ρst α
M+1
|D|C∗.
Additionally, the expected cost of adding the shortest paths from each client j∈Dto the corresponding open
facility σ
U
(j)∈F
U
is at most
∑
j∈Dα
M+1
|D|ℓ(j,F
U
) = α
M+1
|D|C
U
.
Altogether we obtain
E[S]≤Mρst
MS∗+ρst α
M+1
|D|C∗+α
M+1
|D|C
U
≤ρst(S∗+(α+ε)C∗)+ (α+ε)C
U
.
6
Core Detouring Scheme. We next introduce our new core detouring scheme to bound the expected con-
nection cost of
APX
. Notice that, since the clients are assigned to their closest open facility in F, it suffices
to bound the total cost of connecting every client j∈Dto some open facility in F. To this aim, we use the
tree-core connection game introduced in Section 2.
We let the tree-core Tin the game be the tree T∗in the optimum solution and set w(e) = c(e)for every
edge ein the tree. The client nodes simply correspond to the clients in D. We define the mapping µas
the assignment σ∗of
OPT
. For every client node j∈D, the weight of the directed edge (j,µ(j)) ∈Hin is
defined as the connection cost ℓ(j,σ∗(j)); the weight of the directed edge (µ(j),j)∈Hout is ℓ(σ∗(j),j) +
ℓ(j,σ
U
(j)). The sampling probability pis set to p=α/M.
The key-insight now is the following: Fix an outcome of the random sampling. For every flow-path
from a client node j∈Dto a marked client j′∈Din G, there is a corresponding path between jand the
open facility σ
U
(j′)in the original graph; moreover, the costs of these paths are equal. Thus, for every fixed
outcome of the random sampling, the connection cost Cis at most the cost Xof the flow in the tree-core
connection game. Since this holds true for every fixed outcome of the random sampling, it also holds true
unconditionally. We can thus bound the expected connection cost by the expected cost of X; for the latter,
we derived an upper bound in Section 2. The proof of the following lemma now follows easily.
Lemma 3. The connection cost of
APX
satisfies E[C]≤2C∗+C
U
+S∗/α.
Proof. Note that the total weight of the tree-core Tis S∗/M. From the discussion above and Corollary 1 it
follows
E[C]≤E[X]≤w(H)+ 1
p·w(T) = 2∑
j∈D
ℓ(j,σ∗(j))+ ∑
j∈D
ℓ(j,σU(j))+ M
α·S∗
M=2C∗+CU+S∗
α.
Now we have all the ingredients to prove the main result of this paper. The following theorem relies on
the current best approximation factors for Steiner tree and facility location, which are ρst <1.55 [24] and
ρfl<1.52 [18], respectively.
Theorem 4. For a proper choice of α,randCFL is an expected 4.55-approximation algorithm for
CFL
.
Proof. By Lemmas 1, 2, and 3,
E[Z]≤O
U
+ρst(S∗+ (α+ε)C∗)+ (α+ε)C
U
+2C∗+C
U
+S∗/α.
The optimum solution to the facility location problem induced by the input instance is a lower bound on
(C∗+O∗). As a consequence, C
U
+O
U
≤ρfl(C∗+O∗).We thus obtain
E[Z]≤ρst(S∗+(α+ε)C∗)+2C∗+S∗/α+(1+α+ε)ρfl(C∗+O∗)
≤(C∗+O∗)(ρst(α+ε)+ 2+ρfl(1+α+ε))+S∗(ρst +1/α).
Choosing εsufficiently small, and balancing the coefficients of (C∗+O∗)and S∗, we obtain the claimed
approximation ratio for α=0.334.
In the special case of
SROB
, we can assume without loss of generality that the facility location approx-
imation algorithm used in Step 1 of randCFL opens all the facilities. As a consequence, randCFL opens a
facility at every marked client. By imposing O
U
=O∗=C
U
=0 in the analysis of Theorem 4, and choosing
αaccordingly, we obtain the following corollary.
Corollary 3. For a proper choice of α,randCFL is an expected 3.05-approximation algorithm for
SROB
.
7
4.2 Refinements
We can improve the approximation ratio of randCFL by combining the following techniques.
(a) Bifactor facility location. We obtain a better approximation ratio if we run a (proper) bifactor ap-
proximation algorithm on the induced facility location instance in Step 1. An algorithm for the facility
location problem is a (ρO,ρC)-approximation algorithm if, for every feasible solution with opening cost O
and connection cost C, the cost of the solution computed by the algorithm is at most ρOO+ρCC. Mahdian,
Ye, and Zhang [18] give a (1.11,1.78)-approximation algorithm. Moreover, they (essentially) show that
any (ρO,ρC)-approximation algorithm can be converted into a (ρO+lnδ,1+ (ρC−1)/δ)-approximation
algorithm, for any δ≥1.
Note that an optimum solution
OPT
for
CFL
induces a feasible solution for the underlying facility
location problem with opening cost O∗and connection cost C∗. Exploiting this, we obtain
C
U
+O
U
≤(1.11+lnδ)O∗+ (1+0.78/δ)C∗.
We can now optimize the parameter δso as to balance the coefficients of the connection and opening costs;
while the parameter αis used to balance the Steiner and connection costs.
(b) Flow canceling. We can refine Corollary 1, and hence the bound on the connection cost given in
Lemma 3, by means of flow canceling. Consider a given edge eof Tin the tree-core connection game,
and let e1and e2be the two edges of Cassociated to e(because of shortcutting, it might be e1=e2).
If the flows along e1and e2in Care equally directed (and e16=e2), this means that we are sending two
oppositely directed flows along ein T. In this case, it is possible to cancel the difference of the two flows
(independently for each e∈T) by redirecting the flow paths in a proper way. The somewhat technical proof
of the following lemma is given in the Appendix.
Theorem 5. For |D| ≫ 1/p, the cost X of the flow in the tree-core connection game satisfies E[X]≤
w(H)+ 0.807w(T)/p.
In particular, since by assumption |D|/M≫1 and αis a constant, this implies the following refined
bound on the connection cost:
E[C]≤2C∗+C
U
+0.807S∗/α.
Combining Techniques (a) and (b), we obtain the following theorem
Theorem 6. There is an expected 4.00-approximation algorithm for
CFL
. In the special case of
SROB
, the
expected approximation ratio can be reduced to 2.92.
Proof. Let us adapt the proof of Theorem 4. Combining (a) and (b), we obtain
E[Z]≤O
U
+ρst(S∗+ (α+ε)C∗)+ (α+ε)C
U
+2C∗+C
U
+0.807S∗/α
≤ρst(S∗+(α+ε)C∗)+2C∗+0.807S∗/α+(1+α+ε)((1.11+lnδ)O∗+(1+0.78/δ)C∗)
=C∗(ρst(α+ε)+2+ (1+α+ε)(1+0.78/δ))+ S∗(ρst +0.807/α)+ O∗((1+α+ε)(1.11+lnδ))
α=0.330,δ=6.657
<4.00Z∗.
The analysis above can be adapted to
SROB
by imposing C
U
=O
U
=O∗=0. This yields
E[Z]≤ρst(S∗+(α+ε)C∗)+ 2C∗+0.807S∗/αα=0.591
<2.92Z∗.
8
4.3 Derandomization
We can derandomize our algorithm for
CFL
using the method of conditional expectation (see, e.g., [20])
and an idea by van Zuylen and Williamson [27]. Consider any possible choice of a client j1. Intuitively,
j1is the client j∗that we sample uniformly at random. Let j2,j3,..., j|D|be the remaining clients, in an
arbitrary order. Initially, we mark j1. In iteration k,k≥2, we decide whether to mark or unmark client jk.
Let Dk−1be the subset of clients in {j1,j2..., jk−1}that we already marked. Ideally, we would like to mark
client jkif and only if E[Z|Dk=Dk−1∪{ jk}]≤E[Z|Dk=Dk−1].
This would ensure, for a proper choice of j1, that the cost of the final solution is at most 4.00Z∗.
It is not difficult to see that we can efficiently compute the expected opening cost and connection cost,
given Dk. The same holds for the expected augmentation cost in Step 4. The problem is that we do not
know how to compute the conditioned expected cost of the Steiner tree over D. However, as it is shown
by van Zuylen and Williamson [27], we can compute an estimate of this cost if we use a primal-dual 2-
approximation algorithm for the Steiner tree computation instead. In our analysis, we essentially only need
to replace ρst <1.55 by ρst =2, which gives a slightly larger (but deterministic) approximation ratio.
Theorem 7. There is a deterministic 4.23-approximation algorithm for
CFL
. In the special case of
SROB
,
the approximation ratio can be reduced to 3.28.
5 Extensions
Our approach is flexible enough to be adapted to several natural variants of
CFL
. In this section we sketch
two such applications.
5.1 Connected k-Facility Location
An algorithm for
k-CFL
is obtained by modifying randCFL in the following way:
•In Step 1, compute a ρkfl-approximate solution
U
= (F
U
,σ
U
)for the (unconnected) k-facility location
instance induced by the input instance.
This algorithm can be refined using Technique (b). The following theorem relies on the current best approx-
imation ratio for the k-facility location problem, which is ρkfl ≤4 [15, 16] (see also [28]).
Theorem 8. There is an expected 6.85-approximation algorithm for
k-CFL
.
Proof. By adapting the proof of Theorem 6, we obtain
E[Z]≤ρst(S∗+(α+ε)C∗)+ 2C∗+0.807S∗/α+(1+α+ε)ρkfl(C∗+O∗)
≤(C∗+O∗)(ρst(α+ε)+ 2+ρkfl(1+α+ε))+S∗(ρst +0.807/α)α=0.1524
<6.85Z∗.
Also in this case the algorithm can be derandomized by applying the technique by van Zuylen and
Williamson.
Corollary 4. There is a deterministic 6.98-approximation algorithm for
k-CFL
.
9
5.2 Tour-Connected Facility Location
We obtain an algorithm for
tour-CFL
by adapting randCFL in the following way:
•In Step 4, compute a ρtsp-approximate TSP-tour on D. Then augment the tour by adding two shortest
paths between every client in Dand the corresponding open facility in F. Eventually, compute an
Euler tour on the resulting multi-graph and shortcut it to obtain a TSP-tour Tof F.
The algorithm above can be improved by means of Technique (a). The following result relies on Christofides’
1.5-approximation algorithm for metric TSP [5].
Theorem 9. There is an expected 4.12-approximation algorithm for
tour-CFL
.
Proof (sketch). We adapt the analysis of Section 4. Trivially, O≤O
U
. Taking into account the duplication
of the shortest paths from Dto F, and using a similar duplication when bounding the cost of the optimum
TSP-tour over D, we obtain
E[S]≤ρtsp(S∗+2(α+ε)C∗)+ 2(α+ε)C
U
.
We can easily adapt Corollary 1 to this case, thus obtaining E[X]≤w(H)+w(T)/(2p). It follows that
E[C]≤2C∗+C
U
+S∗/(2α).
Altogether
E[Z]≤O
U
+ρtsp(S∗+2(α+ε)C∗)+ 2(α+ε)C
U
+2C∗+C
U
+S∗/(2α)
≤ρtsp(S∗+2(α+ε)C∗) + 2C∗+S∗/(2α)+ (1+2(α+ε))((1+0.78/δ)C∗+(1.11+lnδ)O∗)
=C∗(2ρtsp(α+ε)+ 2+ (1+2(α+ε))(1+0.78/δ))+S∗(ρtsp +1/(2α))
+O∗((1+2(α+ε))(1.11+lnδ)) α=0.19084,δ=6.5004
≤4.12Z∗.
6 Conclusions
We described a simple algorithmic framework, based on random facility sampling, to solve connected facil-
ity location problems. By means of our novel core detouring scheme, we showed that this framework yields
much better approximation algorithms for the family of problems considered.
We leave open thequestion whether core detouring can also be used to obtain significantly better approx-
imation algorithms for
MROB
and the single-sink buy-at-bulk problem. The major difficulty here is that
the optimum solution does not exhibit a single central core. While a small improvement seems nonetheless
possible for the single-sink buy-at-bulk problem, the situation is less clear for
MROB
.
There is a strong relation between random sampling algorithms and the boosted sampling framework for
two-stage stochastic optimization with recourse by Gupta et al. [13]. It is a very interesting open question
whether our core detouring scheme also leads to improved approximation algorithms in that framework.
10
References
[1] M. Andrews and L. Zhang. The access network design problem. In IEEE Symposium on Foundations of Com-
puter Science (FOCS), pages 40–49, 1998.
[2] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verificationand the hardnessof approximation
problems. Journal of the Association for Computing Machinery, 45(3):501–555, 1998.
[3] L. Becchetti, J. K¨onemann, S. Leonardi, and M. P´al. Sharing the cost more efficiently: improved approximation
for multicommodity rent-or-buy. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 375–384.
Society for Industrial and Applied Mathematics, 2005.
[4] M. Bern and P. Plassmann. The Steiner problem with edge lengths 1 and 2. Information Processing Letters,
32(4):171–176, 1989.
[5] N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report,
Graduate School of Industrial Administration, Carnegie-Mellon University, 1976.
[6] S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1:195–207,1971/72.
[7] L. Fleischer, J. K¨onemann, S. Leonardi, and G. Sch¨afer. Simple cost sharing schemes for multicommodity rent-
or-buy and stochastic steiner tree. In ACM Symposium on the Theory of Computing (STOC), pages 663–670.
ACM Press, 2006.
[8] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness.
Freeman, San Francisco, 1979.
[9] A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener. Provisioning a virtual private network: a network
design problem for multicommodity flow. In ACM Symposium on the Theory of Computing (STOC), pages
389–398, 2001.
[10] A. Gupta, A. Kumar, M. Pal, and T. Roughgarden. Approximation via cost-sharing: a simple approximation al-
gorithm for the multicommodity rent-or-buy problem. In IEEE Symposium on Foundations of Computer Science
(FOCS), pages 606–617, 2003.
[11] A. Gupta, A. Kumar, M. Pal, and T. Roughgarden. Approximation via cost-sharing: simpler and better approxi-
mation algorithms for network design. To appear in Journal of the ACM, 2007.
[12] A. Gupta, A. Kumar, and T. Roughgarden. Simpler and better approximation algorithms for network design. In
ACM Symposium on the Theory of Computing (STOC), pages 365–372, 2003.
[13] A. Gupta, M. P´al, R. Ravi, and A. Sinha. Boosted sampling: approximation algorithms for stochastic optimiza-
tion. In ACM Symposium on the Theory of Computing (STOC), pages 417–426. ACM Press, 2004.
[14] A. Gupta, A. Srinivasan, and E. Tardos. Cost-sharing mechanisms for network design. In InternationalWorkshop
on Approximation Algorithms for Combinatorial Optimization, pages 139–150, 2004.
[15] K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. Vazirani. Greedy facility location algorithms analyzed using
dual fitting with factor-revealing lp. Journal of the Association for Computing Machinery, 50:795–824, 2003.
[16] K. Jain and V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the
primal-dual scheme and lagrangian relaxation. Journal of the Association for Computing Machinery, 48:274–
296, 2001.
[17] D. R. Karger and M. Minkoff. Building steiner trees with incomplete global knowledge. In IEEE Symposium on
Foundations of Computer Science (FOCS), pages 613–623, 2000.
[18] M. Mahdian, Y. Ye, and J. Zhang. Improved approximation algorithms for metric facility location problems. In
International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 229–242, 2002.
[19] P. B. Mirchandani and R. L. Francis. Discrete Location Theory. John Wile and Sons, Inc., New York, 1990.
[20] R. Motwani and P. Raghavan. Randomized algorithms. Cambridge University Press, Cambridge, first edition,
1995.
11
[21] C. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Mathematics
of Operations Research, 18:1–11, 1993.
[22] R. Ravi and F. S. Salman. Approximation algorithms for the travelling purchaser problem and its variants in
network design. In European Symposium on Algorithms (ESA), pages 29–40, 1999.
[23] R. Ravi and A. Sinha. Approximation algorithms for problems combining facility location and network design.
Operations Research, 54(1):73–81, 2006.
[24] G. Robins and A. Zelikovsky. Improved Steiner tree approximation in graphs. In ACM-SIAM Symposium on
Discrete Algorithms (SODA), pages 770–779, 2000.
[25] C. Swamy and A. Kumar. Primal–dual algorithms for connected facility location problems. In International
Workshop on Approximation Algorithms for Combinatorial Optimization, pages 256–269, 2002.
[26] C. Swamy and A. Kumar. Primal–dual algorithms for connected facility location problems. Algorithmica,
40(4):245–269, 2004.
[27] A. van Zuylen and D. Williamson. A simpler and better derandomization of an approximation algorithm for
single source rent-or-buy. 2007. To appear in Operations Research Letters.
[28] J. Vygen. Approximation algorithms for facility location problems.
12
C
j i =µ(j)
Figure 1: Core connection game instance. Marked client nodes are drawn in bold. The flow of jin the
routing scheme is indicated by the bold path.
Appendix
Proof of Theorem 5. Our client sampling process is equivalent to
(1) Mark each client independently with probability p.
(2) Choose a client j∗(either marked or not) uniformly at random, and mark it.
Consider the following modified sampling process
(a) Run (1).
(b) If no client is marked in Step (a), run (2).
LetYdenote the cost of the flow in the tree-connection game with respect to the modified sampling scheme.
By a simple coupling argument, it is easy to see that E[X]≤E[Y]. Intuitively, sampling less clients can only
make the cost of the flow larger (in expectation). Hence it is sufficient to bound E[Y].
Let Qdenote the event that in Step (b) of the modified game we run (2). By elementary probability
theory, E[Y] = Pr(Q)E[Y|Q] + Pr(¯
Q)E[Y|¯
Q].
Trivially, Pr(Q) = (1−p)|D|. Moreover,
E[Y|Q]≤w(H)+ |D|w(T)
We will next show that E[Y|¯
Q]≤w(H)+ 0.8067w(T)/p.(2)
From (2) we can conclude that
E[Y]≤w(H)+ w(T)((1−p)|D||D|+0.8067/p)
≤w(H)+ w(T)(e−p|D||D|+0.8067/p)
≤w(H)+ 0.807w(T)/p,
where we used the assumption |D| ≫ 1/p.
13
It remains to prove (2). Subsequently, we assume that the event ¯
Qholds. It is clear that E[f(e)] ≤1
holds for every e∈H. Thus it is sufficient to show that E[f(e)] ≤0.8067/pfor any given e∈T. Let e1
and e2be the two edges of Cassociated to e. We assume by definition that the flow f(ei)along eiin Cis
positive if it goes clockwise, and negative otherwise.
If e1=e2,E[f(e)] = E[|f(e1)|]≤1/(2p)by essentially the standard analysis. Hence, let us assume
e16=e2. In that case F:=f(e) = |f(e1)−f(e2)|by flow canceling. The value of E[F]is a (complicated)
function of p, of m=|D|, and of the distance k, 0 ≤k≤m/2−1, between e1and e2in C.
We first need some notation. Let I,k=|I|, be the shortest path (in terms of number of hops) between e1
and e2along C. Without loss of generality, we assume e1is on the left side of I. Let I′be the complement
of I∪{e1,e2}with respect to C, and k′:=|I′|=m−k−2.
Recall that each node of Cis by-sampled with probability p, but under the event ¯
Qthat at least one
(random) node is by-sampled. We let q=1−p, and distinguish three events A,B, and C, which partition
the probability space considered:
(A) No node selected in I, at least one node selected in I′.The value of Fis deterministically k+1.
In fact, if hflow-paths along Iare directed to the left and the other k+1−hto the right (event A′), then
F1=−h,F2=k+1−h, and altogether E[F|A′] = E[|(−h)−(k+1−h)|] = k+1. Otherwise (event A′′), the
flow on e1and e2must go in the same direction, say from left to right, and it must be f(e2) = f(e1)+ k+1
(e2collects the same flow as e1, plus the flow along I). Then E[F|A′′] = E[|f(e1)−(f(e1)+k+1)|] = k+1.
Since event Ahappens with probability qk+1(1−qk′+1)
1−qm, the overall contribution of this case to the total expected
flow is
FA=Pr(A)E[F|A] = qk+1(1−qk′+1)
1−qm(k+1).
(B) No node selected in I′, at least one node selected in I.By essentially the same argument as in case
(A), we get
FB=Pr(B)E[F|B] = qk′+1(1−qk+1)
1−qm(k′+1).
(C) At least one node selected in both Iand I′.If we denote by Li(Ri) the distance between eiand the
first by-sampled node to its left (right), then E[f(ei)] = (Li−Ri)/2. Variables L1,R1,L2, and R2can be
interpreted as random geometric variables of parameter p, under the constraint that X=L2+R1≤kand
X′=L1+R2≤k′. Let us study the random variables Xand X′. Note that E[F|C] = 1
2E[|X′−X|]. Moreover,
Xand X′are independent. It is not hard to show that
Pr(X=i) = ((i+1)p2qi
1−qk+1if i∈[0,k−1];
(k+1)pqk
1−qk+1if i=k.
Analogously
Pr(X′=j) =
(j+1)p2qj
1−qk′+1if j∈[0,k′−1];
(k′+1)pqk′
1−qk′+1if j=k′.
Note that, as expected, ∑k
i=0Pr(X=i) = ∑k′
j=0Pr(X′=j) = 1. The contribution of this case to the overall
flow is
FC=Pr(C)E[F|C] = (1−qk+1)(1−qk′+1)
2(1−qm)
k
∑
i=0
k′
∑
j=0
|i−j|Pr(X=i)Pr(X′=j).
14
Recall that E[F] = Pr(A)E[F|A]+Pr(B)E[F|B]+Pr(C)E[F|C] = FA+FB+FC. After a simple, but very
long and tedious computation, we obtained
E[F] = −2(k+1)qm
1−qm+2q(1+q+q2)+q2k+2(k2(1−q2)2+k(1−q2)(3−q2)+(2−2q(1+q)2))
p(1−qm)(1+q)3
≤2q(1+q+q2)+q2k+2(k2(1−q2)2+k(1−q2)(3−q2)+(2−2q(1+q)2))
p(1−ε)(1+q)3,
where ε>0 is anarbitrarily small constant. In the last inequality we used the assumptions that αis a positive
constant and m=|D| ≫ 1/p. Consider function
R(q,k):=2q(1+q+q2)
(1+q)3+R′(q,k)
(1+q)3
where
R′(q,k) = q2k+2(k2(1−q2)2+k(1−q2)(3−q2)+ (2−2q(1+q)2)).
It is sufficient to show that R(q,k)≤0.8066 <0.8067 for any qand k. Fixing q, and maximizing in k,
max
0≤k≤k′{R(q,k)} ≤ 2q(1+q+q2)
(1+q)3+1
(1+q)3max
0≤k≤k′{R′(q,k)}
≤2q(1+q+q2)
(1+q)3+1
(1+q)3max
x≥0{R′(q,x)}.
By an elementary analysis of function R′(q,x), we found that it has a maximum (either feasible or not) for
x=x(q):=q2−3
2(1−q2)−1
2lnq−q(1+8q+10q2+8q3+q4)ln2q+ (1−q2)2
2(1−q2)lnq.
Then, by the constraint x≥0, function R′(q,x)is maximized for x=0 if x(q)<0, and for x=x(q)otherwise.
In other words, max
x≥0{R′(q,x)}=R′(q,max{0,x(q)}).
It follows that
max
0≤k≤k′{R(q,k)} ≤ 2q(1+q+q2)
(1+q)3+R′(q,max{1,x(q)})
(1+q)3.
We found numerically that the right-hand side is upper bounded by 0.8066 for any feasible value of q. This
concludes the proof of the theorem.
15
