We study leasing variants of the connected facility location problem, in which we wish to connect a set of clients to facilities, and facilities are connected via core edges, whose cost is a scale factor times the cost of a simple edge. We identify two aspects of the problem that can lead to different variants: (a) if there is a single or multiple commodities, and (b) if we lease facilities and buy core edges, or if we lease both facilities and core edges. Combining these aspects, we propose four variants of the problem, and we give approximation and competitive online algorithms for each of them when the (smallest) scale factor is 1. The algorithms we propose follow the technique of combining available algorithms for the underlying facility leasing and Steiner problems.
In traditional optimization problems, a solution is built by acquiring resources
that persist in time. In leasing optimization problems, some resources may
be leased for different lengths of time and, due to economies of scale, it is more
cost-effective to lease a resource for longer periods. Leasing problems arise, for
example, in the current trend among start-ups that prefer to lease servers in a
cloud service rather than install their own servers [
The parking permit problem (PP) is the fundamental leasing problem.
It was proposed by Meyerson [
by a tree metric [
The connected facility location problem (CFL) is a two-layer network
design problem in which we connect clients via facilities connected through a
core tree. We are given a complete graph G = (V, E) with a metric distance
d : V × V 7→ IR+, a set F ⊆ V of potential facilities with corresponding opening
costs, a root facility r ∈ F , a constant M ≥ 1 and, for t = 1, . . . , T , a set Dt ⊆ V
of clients arriving at instant t. The goal is to select a subset of facilities to open
and a subset of edges that connects open facilities to r, which minimize the cost
of the open facilities, plus M times the cost of the edges that connect
facilities, plus the sum of the distances from each client to its closest open facility.
Grandoni and Rothvoß [
Our contribution We propose leasing variants of CFL and MCFL, and we give approximation and competitive online algorithms for a special case of these problems. The leasing variants we propose model the problem of a network service provider, who has to install cables between routers to serve clients, but resources, such as routers and backbone cables, have different lifetimes which are not negligible.
The first leasing variant of CFL we study is the connected facility leasing
problem (CFLe), whose online version we proposed and addressed in [
The second variant we study is the leasing-connected facility leasing
problem (LeCFLe), in which we lease both facilities and edges connecting
facilities to the root. We have KF types of facility leases, and KE types of
core edge leases. Facilities and core edges may have different leasing lengths.
Instead of a single scaling factor M , we have KE scaling factors γ1E, . . . , γKEE ,
one for each core edge leasing length. Thus, to lease an edge e with leasing
type ke costs γkEe · d(e). We wish to assign an active facility lease to each client
and, for each instant in which a facility serves a client, there must exist a path
of active edge leases from that facility to the root. We wish to minimize the
cost of leasing facilities, plus the cost of connecting clients to facilities, plus
the cost of leasing core edges. For the case in which the smallest edge leasing
scaling factor γ1E is equal to 1, we give a O(KE )-approximation algorithm and a
O(KF lg n + lg KE lg |V |)-competitive online algorithm. The approach is similar
to the one we use for CFLe, but we change the building block algorithm of
the core tree. The offline algorithm uses the O(K)-approximation algorithm
for STLe [
We also study two leasing variants of MCFL: the multi-commodity
connected facility leasing problem (MCFLe), in which facilities are leased but
core edges are permanent, and the multi-commodity leasing-connected
facility leasing problem (MLeCFLe), in which both facilities and core edges
are leased. For MCFLe with M = 1, we give an 8-approximation algorithm,
which combines the 3-approximation for FLeP [
We summarize the approximation/competitive factors we obtain in Table 1.
Our technique for solving these problems for the case with M = 1 (γ1E = 1),
both in offline and online settings, consists in solving the associated facility
leasing problem, buying (leasing) a core network that connects the clients, and then
buying (leasing) core edges between each client and its corresponding facility
lease. The guarantee follows from the analysis of the corresponding building
block algorithms, and from reducing the optimal solution of the connected
facility leasing problem to a feasible solution of the building block problems. This
approach is used in the literature to solve CFL and MCFL when M = 1 [
MLeCFLe O(lg n) if γ1E = 1 O(KF lg n + lg KE lg |V |) if γ1E = 1 2
In CFLe, we are given a complete graph G = (V, E) with a metric distance d : V × V 7→ IR+, a set F ⊆ V of potential facilities, a root facility r ∈ F , K leasing lengths δ1, . . . , δK ∈ IN, a cost γkf ∈ IR+ for leasing facility f ∈ F with leasing type k ∈ [K] (ensuring γkr = 0 for any k), a constant M ≥ 1 and, for t = 1, . . . , T , a set Dt ⊆ V of clients arriving at instant t. For simplicity, we denote by D := {(j, t) : j ∈ Dt for t ∈ [T ]} the set of client requests. The goal is to find a set X ⊆ F × [K] × [T ] of facility leases, a function a : D 7→ X that assigns each client request (j, t) to a facility lease (f, k, tˆ) such that t ∈ [tˆ, tˆ+ δk), and a set T ⊆ E of edges connecting X to r; and we wish to minimize P(f,k,tˆ)∈X γkf + P(j,t)∈D d(a(j, t), j) + M · Pe∈T d(e).
Algorithm 1 is a 7.39-approximation for CFLe when M = 1. First, we obtain
a solution of FLe on the clients, by using the 3-approximation algorithm by
Nagarajan and Williamson [
Let L′ be the facility leasing cost and C′ be the client connection cost of the solution returned by NW-FLe. We have that L + C = L′ + C′ ≤ 3 · optFLe. Since Input: (G, d, F, r, K, δ, γ, M, D1, . . . , DT )
r 1 set γK ← 0; 2 (X, a) ← NW-FLe(G, d, F, K, δ, γ, D1, . . . , DT ); 3 T ← ST(G, d, D ∪ {r}); 4 T ← T ∪ {(j, a(j, t)) : (j, t) ∈ D}; 5 return (X, a, T );
Algorithm 1: Approximation algorithm for CFLe. an optimum solution for CFLe induces a feasible solution for FLe, optFLe ≤ L∗ + C∗, so L + C ≤ 3 · (L∗ + C∗).
Since M = 1, we bound S by the cost of solving ST on D, plus the cost of connecting each client to its assigned facility lease. Thus, S ≤ αST · optST + C. Since the optimum core tree combined with an edge between each client and its optimum facility induces a feasible solution for ST on D, we have that optST ≤ S∗ + C∗ and the theorem follows. ⊓⊔
This algorithm has approximation factor Ω(M ) if M > 1: take an instance
with a single facility f with γ1f = 0 and d(f, r) = 1. Then take one client request
at the same point as f . The algorithm will lease f and connect it to the root, for
a total cost M , while the optimum solution will connect the client to the root
by paying 1. We do not know if there is a constant-approximation algorithm
for CFLe if M > 1. In particular, the technique of sample-and-augment does
not seem to lead to a good approximation algorithm. Suppose an algorithm
which samples each client request with probability 1/M , then solves FLe for
the sampled client requests, buys a core tree between the sampled clients, buys
a core edge between each sampled client and its assigned facility lease, and
finally assigns non-sampled clients to the closest active facility lease. There is
an example which shows that such an algorithm has approximation factor Ω(n)
if M > 1: take a single facility f with d(f, r) = 1, then take K = 1, δ1 = 1,
γ1f = 0, and M = 2. For t = 1, . . . , n with n ≥ 2, take a single client request
at instant t on the same point as f . Note that the optimum solution buys the
core edge (f, r) (cost 2) and always leases facility f (cost zero), paying a total
cost of 2. In expectation, the sample-and-augment algorithm will sample half of
the client requests, buy the core edge, and pay a cost of 1/2 to serve each client
request, since if the client request is not sampled, then it has to be served by
the root. Thus the expected cost is n/2 + 2. Even if one considers more clever
sample-and-augment algorithms for CFL, such as in [
In the online version of CFLe, numbers T and n := Pt=1 |Dt| are unknown.
Sets Dt are revealed one at a time, and we cannot remove edges from T , change
facility leases, or modify a(j, t) once it is chosen. The competitive factor is
Ω(lg K + lg n), due to the lower bounds on PP [
In LeCFLe, we are given a complete graph G = (V, E) with a metric distance d : V × V 7→ IR+, a set F ⊆ V of potential facilities, a root facility r ∈ V , and for t = 1, . . . , T , a set Dt ⊆ V of clients arriving at instant t. However, we may have different leasing types for facilities and core edges. Thus, we are given KF facility leasing lengths δ1F , . . . , δKFF ∈ IN, and leasing facility f ∈ F with leasing type k ∈ [KF ] costs γkf ∈ IR+. We also have KE edge leasing lengths δ1E , . . . , δKEE ∈ IN, edge leasing factors γ1E, . . . , γE KE ≥ 1, and leasing core edge e ∈ E with leasing type ke costs d(e)·γkEe . We wish to find a set X ⊆ F ×[KF ]×[T ] of facility leases, a function a : D 7→ X that assigns a facility lease a(j, t) ∈ X which is active at instant t to each client request (j, t) ∈ D, and a set of edge leases T ⊆ E × [KE] × [T ]. For each client request (j, t) with a(j, t) = (f, k, tˆ), there must exist a path P from f to r in G such that each edge e ∈ P has some edge lease in T which is active at instant t. The goal is to find a solution which minimizes P(f,k,tˆ)∈X γkf +P(j,t)∈D d(a(j, t), j)+P(e,ke,tˆe)∈T γkEe ·d(e). Note that we do not lease edges connecting clients to facilities.4
A standard technique for solving network design problems, especially in an
online setting, is to approximate a metric (or the distances in a graph) by a metric
induced by the distances in a tree. Bartal [
Theorem 2 ([
This theorem is applied by Meyerson [
We propose, in Algorithm 2, an online algorithm for LeCFLe, which is
T
O(KF lg n + lg KE lg |V |)-competitive if γE = 1, where n := Pt=1 |Dt|. The
1
algorithm utilizes as a subroutine the online O(K lg n)-competitive algorithm
for FLe by Nagarajan and Williamson [
Input: (G, d, F, r, KF , δF , γ, KE, δE, γE) 1 T ← ∅; set γKrF ← 0; 2 initialize NW-OFLe with (G, d, F, KF , δF , γ) and let (X, a) be the virtual solution; 3 T ← FRT(V, d); 4 foreach edge e of T do 5 initialize an instance RandOPP[e] with (KE, δE, γE); 6 when Dt arrives do 7 foreach j ∈ Dt do 8 P ← pathT (j, r); 9 foreach edge e ∈ P do 10 send 1 at instant t to RandOPP[e], obtaining a permit (ke, te); 11 T ← T ∪ {(e, ke, te)}; 12 send (j, t) to NW-OFLe and update the virtual solution (X, a); 13 let (f, k, tˆ) ← a(j, t); T ← T ∪ {((f, j), 1, t)}; 14 return (X, a, T );
Algorithm 2: Online algorithm for LeCFLe.
The algorithm builds, utilizing algorithm FRT, a tree T with VT = V
whose distances O(lg |V |)-approximate the distances in G. Then, for each edge of
the tree, the algorithm maintains an instance of algorithm RandOPP. Besides,
similarly to our online algorithm for CFLe [
Theorem 3. Algorithm 2 is O(KF lg n+lg KE lg |V |)-competitive when γ1E = 1. Proof. Given a solution returned by the algorithm, let L be the facility leasing cost, C the client connection cost, and S the core tree cost. Similarly, let L∗, C∗ and S∗ be those costs on an optimum solution.
Let L′ be the facility leasing cost and C′ be the client connection cost of the virtual solution produced by NW-OFLe. We have that L + C = L′ + C′ = O(K lg n) · optFLe. Since an optimum solution for CFLe induces a feasible solution for FLe, optFLe ≤ L∗ + C∗, so L + C = O(K lg n) · (L∗ + C∗).
We bound S by the cost of solving SLe on D, plus the cost of an edge lease of type 1 between each client and its assigned facility lease, which is the connection cost for that client since γE = 1. Thus, S ≤ O(lg KE lg |V |) · optSLe + C. Since 1 the optimum core tree combined with an edge lease of type 1 between each client and its optimum facility induces a feasible solution for SLe on D, we have that optSLe ≤ S∗ + C∗ and the theorem follows. ⊓⊔
If we substitute algorithm ST with the algorithm by Anthony and Gupta for
STLe, which is a O(K)-approximation [
In MCFLe, the input consists of a complete graph G = (V, E), a metric distance d : V × V 7→ IR+, a set F ⊆ V of potential facilities, K facility leasing lengths δ1, . . . , δk ∈ IN, a cost γkf ∈ IR+ for leasing facility f ∈ F with leasing type k ∈ [K], a constant M ≥ 1 and a sequence P1, . . . , PT ⊆ V × V of sets of pairs of clients. We denote by F := F × [K] × [T ] the set of possible facility leases. Let X ⊆ F , T ⊆ E, u, v ∈ V and t ∈ [T ]; we denote by dX,T (u, v, t) the distance between u and v in the graph in which we add to G edges of cost zero between each pair of facility leases in X that are in the same tree in T and that are active at instant t. We also denote by P := {(u, v, t) : (u, v) ∈ Pt for t ∈ [T ]} the set of client pair requests. The goal is to find a set X ⊆ F of facility leases and a forest T ⊆ E which minimize P(f,k,tˆ)∈X γkf +P(u,v,t)∈P dX,T (u, v, t)+M ·Pe∈T d(e) .
In this section we present an offline and an online algorithm for problem
MCFLe, which are extensions of Algorithm 1 and of algorithm SimpleOCFLe
presented in [
We present, in Algorithm 3, an offline algorithm for MCFLe. The algorithm
runs an instance of the 3-approximation primal-dual algorithm for FLeP [
Input: (G, d, F, K, δ, γ, M, P1, . . . , PT ) 1 foreach (u, v) ∈ Pt do set π(u, t) ← π(v, t) ← d(u, v)/2; 2 let Dt ← S(u,v)∈Pt{u, v}; 3 (X′, a′) ← Primal-DualFLeP(G, d, F, K, δ, γ, D1, . . . , DT , π); 4 D′ ← {{(u, t), (v, t)} : (u, v) ∈ Pt : a′(u, t) 6= null and a′(v, t) 6= null}; 5 X ← {(f, k, tˆ) ∈ X : ∃(u, t) ∈ D : a′(u, t) = (f, k, tˆ)};
′ ′ 6 T ← SF(G, d, D′) ∪ {(u, a′(u, t)) : (u, t) ∈ D′}; 7 return (X, T );
Algorithm 3: Approximation algorithm for MCFLe.
Theorem 4. Algorithm 3 is an 8-approximation if M = 1.
Proof. Given a solution returned by the algorithm, let L be the facility leasing cost, C the client connection cost, and S the core tree cost. Similarly, let L∗, C∗ and S∗ be those costs on an optimum solution.
Let L′ be the facility leasing cost, C′ be the client connection cost, and Π′ be the penalty cost of the solution returned by Primal-DualFLeP on D := StT=1 Dt. We have that L′ + C′ + Π′ ≤ 3 · optFLeP. Given an optimum solution for MCFLe on P, we obtain a feasible solution for FLeP on D by paying the penalties for the clients in the pairs that are connected directly, and by assigning the other clients to the closest facility lease in the path connecting the pair. Thus, optFLeP ≤ L∗ + C∗ and L′ + C′ + Π′ ≤ 3 · (L∗ + C∗). ′ Since Algorithm 3 leases a subset of the facility leases in X′, clearly L ≤ L .
For a request (u, v, t) connected directly by Algorithm 3, we have that one of (u, t) and (v, t) pays for its penalty cost. Suppose w.l.o.g. that it is (u, t); then dX,T (u, v, t) ≤ 2 · π(u, t). For a request (u, v, t) connected through the core tree, our algorithm adds to the tree a whole path between a′(u, t) and a′(v, t), so dX,T (u, v, t) ≤ d(u, a′(u, t)) + d(v, a′(v, t)). Thus C ≤ 2 · Π′ + C′.
Since M = 1, we bound S by the cost of solving SF on D′, plus the cost of connecting each client in D′ to its assigned facility lease. Thus, S ≤ 2·optSF(D′)+ C′ ≤ 2 · optSF(P) + C′. Since the optimum core tree combined with the optimum client connection edges induces a feasible solution for SF on P, we have that optSF(P) ≤ S∗ + C∗. Substituting the previous inequalities, we have that L + C + S ≤ L′ + 2 · Π′ + C′ + 2 · (S∗ + C∗) + C′ ≤ 2 · (S∗ + C∗) + 2 · (L′ + Π′ + C′) ≤ 2 · (S∗ + C∗) + 6 · (L∗ + C∗) ≤ 8 · (L∗ + C∗ + S∗) .
⊓⊔ T
In the online version of MCFLe, numbers T and n := Pt=1 |Dt| are unknown, sets Pt are revealed one at a time, and we must return sequences of sets X1, . . . , XT ⊆ F and T1, . . . , TT ⊆ E, where Xt ⊇ Xt−1 and Tt ⊇ Tt−1 for t = 2, . . . , T , and for t = 1, . . . , T , we must build Xt, Tt only with the information of P1, . . . , Pt, X1, . . . , Xt, T1, . . . , Tt. Also, the objective function is slightly different: minimize P(f,k,tˆ)∈XT γkf + P(u,v,t)∈P dXt,Tt (u, v, t) + M · Pe∈TT d(e); i.e., we can only use facility leases and core edges bought up to instant t to connect clients arriving at instant t.
We give the following online algorithm for this problem. The algorithm
combines ideas from Algorithm 3 and algorithm SimpleOCFLe [
Input: (G, d, F, K, δ, γ, M ) 1 X1 ← ∅, T1 ← ∅; 2 initialize SFCLWF-OFLeP with (G, d, F, K, δ, γ); let (X′, a′) be the virtual solution; 3 initialize BC-OSF with (G, d) and let T ′ be the virtual solution; 4 when Pt arrives do 5 if t > 1 then Xt ← Xt−1, Tt ← Tt−1; 6 foreach (u, v) ∈ Pt do 7 set π(u, t) ← π(v, t) ← d(u, v)/2; 8 send (u, t, π(u, t)) and (v, t, π(v, t)) to SFCLWF-OFLeP and update the virtual solution (X′, a′); 9 if a′(u, t) 6= null and a′(v, t) 6= null then 10 Xt ← Xt ∪ {a′(u, t), a′(v, t)}; 11 send (u, v) to BC-OSF and update the virtual solution T ′; 12 Tt ← Tt ∪ T ′ ∪ {(u, a′(u, t)), (v, a′(v, t))}; 13 return (X1, . . . , XT , T1, . . . , TT );
Algorithm 4: Online algorithm for MCFLe.
Theorem 5. Algorithm 4 is O(K lg n)-competitive if M = 1.
Proof. Given a solution returned by the algorithm, let L be the facility leasing cost, C the client connection cost, and S the core tree cost. Similarly, let L∗, C∗ and S∗ be those costs on an optimum solution.
Denote by D the set of client requests as in Line 8 of the algorithm. Let L′ be the facility leasing cost, C′ be the client connection cost, and Π′ be the penalty cost of the virtual solution produced by SFCLWF-OFLeP on D. We have that L′ + C′ + Π′ = O(K lg n) · optFLeP. Given an optimum solution for MCFLe on P, we obtain a feasible solution for FLeP on D by paying the penalties for the clients in the pairs that are connected directly, and by assigning the other clients to the closest facility lease in the path connecting the pair. Thus, optFLeP ≤ L∗ + C∗ and L′ + C′ + Π′ = O(K lg n) · (L∗ + C∗). ′ Since Algorithm 4 leases a subset of the facility leases in X′, clearly L ≤ L .
For a request (u, v, t) connected directly by Algorithm 4, we have that one of (u, t) and (v, t) pays for its penalty cost. Suppose w.l.o.g. that it is (u, t); then dXt,Tt(u, v, t) ≤ 2 · π(u, t). For a request (u, v, t) connected through the core tree, our algorithm adds to the tree a whole path between a′(u, t) and a′(v, t), so dXt,Tt(u, v, t) ≤ d(u, a′(u, t)) + d(v, a′(v, t)). Thus C ≤ 2 · Π′ + C′.
Let D′ be the set of client requests that are connected through the core tree in Line 12 of Algorithm 4. Since M = 1, we bound S by the cost of the virtual solution produced by BC-OSF on D′, plus the cost of connecting each client in D′ to its assigned facility lease. Thus, S ≤ O(lg n) · optSF(D′) + C′ ≤ O(lg n)· optSF(P)+ C′. Since the optimum core tree combined with the optimum client connection edges induces a feasible solution for SF on P, we have that optSF(P) ≤ S∗ + C∗ and the theorem follows. ⊓⊔
Due to space constraints, we omit the presentation of the offline and
online algorithms for MLeCFLe, since they follow the ideas in the algorithms
for LeCFLe and MCFLe. Note, however, that the algorithm by Anthony and
Gupta [
Future work includes to obtain good approximation and competitive online
algorithms for connected facility leasing problems in the case when the (smallest)
scale factor is greater than 1, which is an open question. Another research
direction is to study connected facility location problems in variations of the leasing
model, such as when a demand has a time window to be served after its
arrival [