Facility Leasing with Penalties
Murilo S. de Lima∗1 , Mário C. San Felice†2 , and Orlando Lee‡1
1

2

Institute of Computing, University of Campinas (Unicamp)
Institute of Mathematics and Statistics, University of São Paulo (USP)

arXiv:1610.00575v1 [cs.DS] 3 Oct 2016

December 27, 2017
Abstract
In this paper we study the facility leasing problem with penalties. We present a primaldual algorithm which is a 3-approximation, based on the algorithm by Nagarajan and
Williamson for the facility leasing problem [NW13] and on the algorithm by Charikar et al.
for the facility location problem with penalties [CKMN01].

1

Introduction

In the facility location problem, one is given a set F of facilities, an opening cost for each
facility, a set D of clients and a metric distance function d between facilities and clients. The
objective is to choose a subset of the facilities to open and an assignment between clients and
facilities, so to minimize the cost of opening the facilities plus the sum of the distances between each client and the corresponding assigned facility. This is an NP-hard problem, and it
does not have a polynomial-time algorithm with approximation factor smaller than 1.463 unless P = NP [Svi02]. Currently the best approximation factor is 1.488, due to an algorithm by
Li [Li13].
In the facility location problem with penalties, we may not assign a client j to a facility if we
choose to pay a penalty πj . I.e., we must select a subset of the facilities to open, and a subset
of the clients we assign to open facilities; we are going to pay the penalties for the remaining
of the clients. The cost of a solution is, therefore, the cost of opening the selected facilities,
plus the distance between the client and its corresponding facility for each assigned client, plus
the penalty cost for each unassigned client. Clearly the facility location problem reduces to this
problem if we set πj = ∞ for every client j. Currently it is known a 1.5148-approximation
algorithm for this problem [LDXX15]; however, there is a simpler 3-approximation algorithm by
Charikar et al. [CKMN01]. Also, if the penalties obey a submodular function, then there is a
2-approximation algorithm [LDXX15].
In the facility leasing problem, client requests are distributed along the time, and instead
of opening facilities permanently, we may lease each facility for one of K different durations
δ1 , . . . , δK . The cost for leasing a facility for δk units of time depends on the facility position,
as in the traditional facility location problem, but also on the leasing type k. Additionally, it
is reasonable to suppose that the leasing costs respect an economics of scale: the leasing cost
per unit of time decreases with the leasing duration, for a fixed facility location. A facility lease
may begin at any moment in the time. Then, we wish to select a set of facility leases that cover
the client requests and minimizes the leasing costs plus the distance between each client and
∗

mslima@ime.usp.br Supported by FAPESP PhD Scholarship Process 2014/18781-1, and CNPq PhD Scholarship Process 142161/2014-4.
†
felice@ic.unicamp.br Supported by CAPES PNPD scholarship 1522390.
‡
lee@ic.unicamp.br Partially supported by Bolsa de Produtividade do CNPq Process 311373/2015-1, and
Edital Universal CNPq Process 477692/2012-5.

1

the facility lease that serves each of its requests. This problem was proposed by Nagarajan and
Williamson, who presented a simple 3-approximation primal-dual algorithm [NW13].
In this paper, we study the combination of the previous two problems, which we call the
facility leasing problem with penalties (PFLe). In this problem, facilities are leased instead of permanently opened, as in the facility leasing problem, and some clients may be left
unassigned by paying for the penalty cost. We obtain a 3-approximation algorithm by combining the algorithm by Nagarajan and Williamson for the facility leasing problem [NW13] and the
algorithm by Charikar et al. for the facility location problem with penalties [CKMN01].
The leveraging scheme by Li et al. [LDXX15] implies that, for any covering problem with
an α-approximation algorithm, there is a (1 − e−1/α )−1 -approximation algorithm for the corresponding covering problem with submodular penalties. Combining this with the algorithm by
Nagarajan and Williamson (α = 3), one may obtain a 3.5277-approximation algorithm for the
facility leasing problem with submodular penalties. Note that our algorithm obtains a better
approximation ratio for the linear case.

2

Notation and Problem Definition

Let [K] := {1, . . . , K} be the set of lease types. We denote a facility lease by a triple
f = (pf , kf , tf ), where pf ∈ V is the point where f is located, kf ∈ [K] is the leasing type for f ,
and tf ∈ Z+ is the instant of time in which the lease for f begins. We write F := F × [K] × Z+
so to simplify our notation.
Similarly, we denote a client by a triple j = (pj , πj , tj ), where pj ∈ V is the point where j
is located, πj ∈ R+ is the penalty for not assigning a facility lease to j, and tj is the instant in
which j arrives.
In order to simplify our notation, we write δf instead of δ(kf ), and γf instead of γ(pf , kf ),
for a facility lease f = (pf , kf , tf ) ∈ F. Also, for f = (pf , kf , tf ) ∈ F and j = (pj , πj , tj ) ∈
V × R+ × Z+ , we define the distance between j and f to be

d(pj , pf ) if tj ∈ [tf , tf + δf ),
d(j, f ) :=
∞
otherwise.
I.e., the distance between client j and facility lease f is infinity if the facility lease does not
cover tj .
Problem PFLe(V, d, F, K, γ, δ, D): The input consists of a set of points V , a distance
function d : V × V 7→ R+ between the points of V satisfying symmetry and triangle
inequality, a set F ⊆ V of potential facilities, an integer K > 0 that represents the
number of lease types, a cost γ(p, k) ∈ R+ for leasing facility p ∈ F with leasing type
k ∈ [K], a function δ : [K] 7→ N that maps each lease type to a length in days, and a
set D ⊆ V × R+ × Z+ of clients in the form j = (pj , πj , tj ). The goal is to find a set
X ⊆ F := F × [K] × Z+ of facility leases in the form f = (pf , kf , tf ), and a function
a : D 7→ X ∪ {null} that maps each client j to an active facility leasing f ∈ X such that
tj ∈ [tf , tf + δf ) or to null, so to minimize
X
X
X
γf +
d(j, a(j)) +
πj .
f ∈X

j∈D:a(j)6=null

j∈D:a(j)=null

2

3

Primal-Dual Formulation
• Primal:
P
P
P
P
minimize
f ∈F γf · yf +
j∈D
f ∈F d(j, f ) · xjf +
j∈D πj · zj
subject to P
xjf ≤ yf
∀f ∈ F, j ∈ D
x
+
z
≥
1
∀j
∈D
j
fj
f ∈F
tj ∈[tf ,tf +δf )

xf j , yf , zj ∈ {0, 1} ∀f ∈ F, j ∈ D

(Variable yf indicates whether facility f was leased, variable xjf indicates whether client j
was served by facility lease f , and variable zj indicates whether the algorithm decided to
pay the penalty associated with not serving j with a facility lease.)
• Dual relaxation:
maximize
subject to

P

P

j∈D

αj

j∈D (αj

− d(j, f ))+ ≤ γf ∀f ∈ F
αj ≤ πj ∀j ∈ D
αj ≥ 0 ∀j ∈ D

(Economical interpretation: each client j is willing to pay αj to connect itself to some
facility lease. Part of this value covers the distance to the facility; the other part is a
contribution to pay for leasing the facility. However, the client is not willing to pay more
than its penalty.)

4

Algorithm

Our algorithm is based on the algorithm by Nagarajan and Williamson for the facility leasing
problem [NW13], and on the algorithm by Charikar et al. for the facility location problem with
penalties [CKMN01]. We say that a client j reaches a facility lease f if αj ≥ d(j, f ).
Algorithm Primal-DualPFLe(V, d, F, K, γ, δ, D)
01 set αj ← 0 for every j ∈ D
02 X ← ∅, S ← D
03 while S 6= ∅ do
04
increase αj uniformly for every j ∈ S until
05
(a) αj = d(j, f ) for some j ∈ S and f ∈ X
06
or
P
07
(b) γf = j∈D (αj − d(j, f ))+ for some f ∈ F \ X
08
or
09
(c) αj = πj for some j ∈ S
10
X ← X ∪ {f ∈ F \ X : f satisfies (b)}
11
S ← S \ {j ∈ S : αj ≥ πj or j reaches some f ∈ X}
12 build the graph GX with
13
V [GX ] ← X
14
E[GX ] ← {(f, f ′ ) : ∃j ∈ D : j reaches both f and f ′ }
15 build a maximal independent set X ′ in GX greedily in decreasing order of δ
16 X̂ ← {(pf , kf , tf − δk ), f, (pf , kf , tf + δk ) : f ∈ X ′ }

3

17
18
19
20
21
22

for every j ∈ D do
if j reaches some f ∈ X then
a(j) ← arg minf ′ ∈X̂ {d(j, f ′ )}
else
a(j) ← null
return (X̂, a)

The algorithm maintains a dual variable αj for each client j ∈ D, a set X of temporarily
leased facilities, and a set S of the clients whose dual variable still is being increased, which is
initialized with the whole set of clients D. The increasing pauses when either: (a) a client reaches
an already temporarily leased facility, (b) the sum of the contributions towards a facility lease
pays for its cost or (c) the dual variable reaches the penalty cost for some client. We then add
to X the facilities that reach condition (b). Also, we remove from S the clients that reach some
temporarily leased facility or whose dual variable pays for the penalty cost, and then proceed
the increasing of the remaining dual variables until S becomes empty.
After that initial phase, we build an interference graph GX between the facility leases in X.
Graph GX has vertex set X and has an edge between facilities f and f ′ if there is some client
that reaches both f and f ′ . Then, we order set X by decreasing order of lease duration and build
a maximal independent set X ′ in a greedily manner; i.e., we visit set X in that order and add a
facility f to X ′ if there is no other facility lease f ′ ∈ X ′ reached by some client that reaches f .
Thus X ′ satisfies the following properties:
1. Every client reaches at most one facility lease in X ′ ;
2. If facility leases f and f ′ in X are reached by the same client j, and if f ′ ∈ X ′ , then
δf ≤ δf ′ .
However, note that there may be some client j that reaches some f in X but is not covered
by any facility lease in X ′ . But then remember that some f ′ ∈ X ′ shares a reaching client j ′
with f , thus δf ≤ δf ′ and the intervals covered by facility leases f and f ′ overlap. Then, since
we buy X̂, which has three copies of f ′ , beginning at instants tf ′ − δf ′ , tf ′ and tf ′ + δf ′ , we have
that the interval formed by those three facilities, which is [tf ′ − δf ′ , tf ′ + 2δf ′ ), is a superset of
interval [tf , tf + δf ), and therefore one of them covers tj .
Finally, if some client j does not reach any facility lease in X, then its dual variable pays for
its penalty and we set a(j) to null.
Also, note that, although the number of potential facility leases is infinite, the algorithm
may be implemented in finite time, which is also polynomial in the input size: it is enough to
consider, for every facility point, a lease beginning at each instant in which we have a client
request.

5

Analysis

In this section we analyze the approximation factor of algorithm Primal-DualPFLe.
First note that, since the conditions (a), (b) and (c) correspond to constraints of the relaxation of the dual program, we have that α is a feasible dual solution. Therefore, by weak duality,
we have that
X
αj ≤ opt(V, d, F, K, γ, δ, D).
j∈D

We will show, then, that the cost of the primal solution (X̂, a) returned by the algorithm is
at most 3 times the cost of the dual solution, and thus our algorithm is a 3-approximation to
problem PFLe.
4

F
P
For every client j ∈ D, we define numbers αC
j , αj , and αj in the following manner:

1. If j reaches some f ∈ X ′ , then let
αC
j := d(j, f ),

αFj := αj − d(f, j),

αPj := 0;

2. If j does not reach any facility lease in X ′ but reaches some f ∈ X, then we let
αC
j := αj ,

αFj := 0,

αPj := 0;

3. Finally, if j does not reach any facility lease in X, then we let
αC
j := 0,

αFj := 0,

αPj := αj .

Note that, either case, we have that
F
P
αj = αC
j + αj + αj .

Now, first let us bound the facility leasing cost. Note that, by construction, we have that, for
every f ∈ X ′ , every client that reaches f reaches only f in X ′ . Also, by case (b) of the algorithm,
the leasing cost of f is totally paid by contributions from clients that reach f . Therefore, we
have that
X
X
γf =
αFj .
f ∈X ′

j∈D

Since X̂, which is the set of facility leases actually bought by the algorithm, consists of three
copies of each facility lease in X ′ , we have that
X
X
γf ≤ 3 ·
αFj .
j∈D

f ∈X̂

Now we bound the penalty cost. We have that a client j has a(j) set to null if and only if it
does not reach any facility lease in X, and then αj = αPj . Also, due to case (c) of the algorithm,
we have that αj = πj . Thus, it is straightforward to conclude that
X
X
πj =
αPj .
j∈D

j∈D:a(j)=null

Finally, we have to bound the client connection cost. Let DX ′ be the set of clients that reach
some facility in X ′ . Note that those clients are connected to the closest facility lease in X̂. Since
every such client j reaches some f ∈ X ′ , we have that
d(j, a(j)) ≤ d(j, f ) = αC
j .
Now let j be some client that reaches some f ∈ X but does not reach any facility lease in X ′ .
There must be some f ′ ∈ X ′ and some j ′ that reaches both f and f ′ , by construction of X ′ . But
then we must have that αj ≥ αj ′ , since when αj ′ stopped increasing it reached both f and f ′ ,
and αj reached f when it stopped increasing. Then, since j ′ reaches both f and f ′ , we have that
αj ′ ≥ d(j ′ , f ) and αj ′ ≥ d(j ′ , f ′ ).
Since one of the three copies of f ′ in X̂ must cover tj , by triangle inequality, we have that
d(j, a(j)) ≤ d(j, f ′ ) ≤ d(j, f ) + d(j ′ , f ) + d(j ′ , f ′ ) ≤ αj + αj ′ + αj ′ ≤ 3 · αj = 3 · αC
j .
Summing up the previous inequalities, we have that
X
X
X
X
γf +
d(j, a(j)) +
πj ≤ 3 ·
αj ≤ 3 · opt(V, d, F, K, γ, δ, D),
f ∈X̂

j∈D:a(j)6=null

j∈D:a(j)=null

j∈D

and we conclude the following theorem.
Theorem 1: Algorithm Primal-DualPFLe is a 3-approximation.
5

References
[CKMN01] M. Charikar, S. Khuller, D. M. Mount, and G. Narasimhan. Algorithms for facility
location problems with outliers. In SODA’01: Proceedings of the 12th Annual ACMSIAM Symposium on Discrete Algorithms, pages 642–651, 2001.
[LDXX15] Y. Li, D. Du, N. Xiu, and D. Xu. Improved approximation algorithms for the facility
location problems with linear/submodular penalties. Algorithmica, 73(2):460–482,
2015.
[Li13]

S. Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45–58, 2013.

[NW13]

C. Nagarajan and D. P. Williamson. Offline and online facility leasing. Discrete
Optimization, 10(4):361–370, 2013.

[Svi02]

M. Sviridenko. An improved approximation algorithm for the metric uncapacitated
facility location problem. In W. J. Cook and A. S. Schulz, editors, Integer Programming and Combinatorial Optimization, volume 2337 of Lecture Notes in Computer
Science, pages 240–257. Springer Berlin Heidelberg, 2002.

6

