See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/228920978

Facility location and covering problems

Article · January 2004

CITATIONS READS

7 2,244

2 authors:

Jurij Mihelič Borut Robic

University of Ljubljana University of Ljubljana
49 PUBLICATIONS 175 CITATIONS 132 PUBLICATIONS 1,280 CITATIONS

SEE PROFILE SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Parallel Computing View project

Computability Theory View project

All content following this page was uploaded by Borut Robic on 04 June 2014.

The user has requested enhancement of the downloaded file.

 Facility Location and Covering Problems

Jurij Mihelič Borut Robič

Faculty of Computer and Information Science Faculty of Computer and Information Science
University of Ljubljana University of Ljubljana
Tržaška 25, Ljubljana, Slovenia Tržaška 25, Ljubljana, Slovenia
jurij.mihelic@fri.uni-lj.si borut.robic@fri.uni-lj.si

ABSTRACT the covering problems and the results about them can be
We discuss the connection between facility location prob- used for solving the facility location problems. Sometimes
lems and covering problems, and present approaches to these reductions are very straightforward. In the next sec-
solving facility location problems by reducing them to cov- tion we describe several facility location problems and their
ering problems. In particular, we discuss the following relations to some covering problems. In particular, we dis-
N P -hard optimization problems: the set cover and the re- cuss the set cover and the related facility location problem,
lated set cover facility location problem, the k-center and the k-center and k-suppliers problem, the dominating set
k-suppliers problem, the dominating set problem, the max- problem, the independent set problem, and the maximum
imum independent set problem, and the maximum covering covering problem.
problem.
2. FACILITY LOCATION AND COVERING
Keywords In this section we present several ways of solving facility
combinatorial optimization, approximation algorithms, fa- location problems using methods for solving covering prob-
cility location, covering problems lems.

1. INTRODUCTION 2.1 Facility Location and Set Cover Problem

Facility location is an important research area of environ- Consider the following facility location problem [2, 4]. Given
ment engineering, regional and city planning, management a complete network G = (V, E) and a coverage distance D,
and transportation science and other fields with a lot of find the minimum cardinality set S ⊆ V , such that for ev-
applications [2, 4, 11]. Often facility location and covering ery v ∈ V − S there is some u ∈ S so that d(u, v) ≤ D, i.e.
problems are N P -hard. Thus, exact solutions are not ex- find the minimum cardinality subset S of vertices V such
pected to be found easily. Thus, finding several different that the distance from every vertex in V to some vertex in
ways of solving these problems is important in view of the S is at most D. We call this problem the set cover facility
efficiency of the solutions found. In this article we present location problem. In the following we show that it is actu-
several facility location problems and a way of solving them ally the set cover problem defined in the graph-theoretical
by using (i.e. transforming to) the covering problems. domain.

Our view of the facility location problems is graph-theore- To obtain the set cover problem from the set cover fa-
tical, although the problems can also be defined in continu- cility location problem, we construct the family of sets
ous or discrete domain [2]. Usually, the environment of the {S1 , S2 , . . . , Sn } where Su = {v ∈ V |d(u, v) ≤ D}, i.e.
facility location problem is defined as a simple clique G = Su contains all vertices which are covered by the vertex
(V, E), i.e. a complete graph with no loops. Edges e ∈ E of u. Notice that V = ∪u∈V Su . The corresponding set
G have weights w(e), which may represent travel distances cover problem is to find the minimum cardinality set S ⊆
or service times from one vertex to another, i.e. from a fa- {S1 , S2 , . . . , Sn } such that all vertices v ∈ V are covered,
cility to a client. Such a weighted graph is called network. i.e. V = ∪Su ∈S Su .
Often the triangle inequality is required, i.e. w(euv ) ≤
w(euw ) + w(ewv ), which is usually a realistic assumption. Using this reduction one can also easily solve the set cover
facility location problem with additional constraint where
In this article we show the connection between facility lo- vertices of possible locations of facilities are specified. To
cation problems and the covering problems, i.e. the way do this, we construct the family of sets {S1 , S2 , . . . , S|F | },
where F ⊆ V is the set of vertices representing possible
Theoretical Computer Science, Information Society facility locations and Su = {v ∈ F |d(u, v) ≤ D}, and use it
2004, Ljubljana, Slovenia, October 11-15, 2004 with the corresponding set cover problem.

Additionally, one can also specify the price wv , v ∈ V

of opening a facility at the vertex v. Then by using the
weighted set cover problem one can minimize the total price
of opened facilities in order to cover all clients.

2.2 k-Center and Set Cover Problem

In this subsection we describe the reduction from the k-
center facility location problem to the set cover facility lo-
cation problem [2, 4, 10].
Given a completeViewnetwork
publication stats
G = (V, E), the k-center prob- polynomial 2-approximation algorithm since maximal inde-
lem is to find S ⊆ V , where |S| ≤ k, which minimizes pendent set is one of suboptimal solutions of the maximum
maxv∈V minu∈S d(u, v). independent set problem.

In the following we describe the so-called bottleneck tech- 2.5 k-Center and Maximum Covering
nique [6], which is often used to solve the k-center prob-
lem. We assume w.l.g. that edges E = {e1 , e2 , . . . , em }
Problem
are sorted in nondecreasing order by their weights, i.e. Let use first define the maximum covering facility location
w(ei ) ≤ w(ei+1 ). Let the bottleneck graph be the graph problem. Given a complete network G = (V, E) and posi-
Gi = (V, Ei ), where Ei = {e1 , e2 , . . . , ei }, i.e. Gi is a tive parameters k and D, the task is to find S ⊆ V , where
subgraph of G containing only edges whose weights are |S| ≤ k, such that S maximizes the number of covered
at most w(ei ). The bottleneck technique is to iteratively clients, i.e. the number of vertices whose distance from S
consider bottleneck graphs G1 , G2 , . . . , Gm . Instead of it- is at most D.
erative search often binary search is used to speed up the
search process through the bottleneck graphs. At each step Again, we use bottleneck technique to solve the k-center
of the search (i.e. for each bottleneck graph Gi ), we exam- problem [3]. For each Gi we find the solution S of the
ine Gi for the feasible solution(s). maximum covering facility location problem. If |S| = n, i.e.
if all clients are covered then S is also a feasible solution of
For Gi we consider the solution S of the set cover facility the k-center problem.
location problem. If |S| ≤ k, we accept S as the feasible
solution of the k-center problem; otherwise, we continue 3. CONCLUSIONS
and consider the next bottleneck graph. In this article we discussed several ways of solving facil-
ity location problems by using covering problems. Because
all the presented optimization problems are N P -hard, dif-
2.3 k-Suppliers and Set Cover Problem ferent algorithms for the given problem may considerably
The k-suppliers facility location problem is similar to the differ in the quality of their (suboptimal) solutions.
k-center problem [5] and is defined as follows. Given a com-
plete bipartite network G = (U, V, E), where U is the set 4. REFERENCES
of possible center locations, and V is the set of clients, find [1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and
the set S ⊆ U which minimizes maxv∈V minu∈S d(u, v). C. Stein. Introduction to Algorithms. The MIT Press,
2nd edition, 2001.
By using the bottleneck technique we can also solve the k-
suppliers problem. The only difference is to consider only [2] M. S. Daskin. Network and Discrete Location: Models
vertices in U , i.e. for the set cover problem construct only Algorithms and Applications. Wiley, New York, 1995.
sets Su where u ∈ U .
[3] M. S. Daskin. A new approach to solving the vertex
There are several ways to solve the set cover problem. One p-center problem to optimality: Algorithm and
may use greedy algorithm [1], elimination heuristic [7] or computational results. Communications of the
zero-one integer linear programming [2, 4]. Operations Research Society of Japan, 45:9:428–436,
2000.

2.4 k-Center and Dominating Set Problem [4] Z. Drezner and H. W. Hamacher, editors. Facility
In this subsection we describe how to solve the k-center Location: applications and theory. Springer-Verlah,
problem using the dominating set problem. Let us first de- Berlin, 2002.
fine the dominating set problem. Given a graph G = (V, E) [5] D. S. Hochbaum, editor. Approximation Algorithms
the dominating set problem is to find minimum cardinality for NP-hard Problems. PWS publishing company,
set S ⊆ V , such that every vertex in V − S is adjacent to Boston, 1995.
some vertex in S.
[6] D. S. Hochbaum and D. B. Shmoys. A unified
Again, we apply bottleneck technique for solving the k- approach to approximation algorithms for bottlneck
center problem. The solution of the k-center problem is problems. J. of ACM, 33:533–550, 1986. PR.
the dominating set S of the bottleneck graph Gj , where [7] J. Mihelič. Hevristično reševanje problemov
|S| ≤ k and j is the smallest index such that Gj contains a pokrivanja in razmeščanja. Fakulteta za
dominating set with at most k vertices. Notice that there računalništvo in informatiko, Univerza v Ljubljani,
are well-know algorithms for computing small dominating 2004. (Magistrsko delo).
sets [1, 8, 9].
[8] J. Mihelič and B. Robič. Approximation algorithms
If the triangle inequality is assumed, one can construct a for k-center problem: an experimental evaluation.
2-approximation algorithm for the k-center problem in the Proc. OR 2002, Klagenfurt, Austria, 2002.
following way. Find the maximal independent set I in the
square G2i of the bottleneck graph Gi . The set I is the [9] J. Mihelič and B. Robič. Solving the k-center
approximate solution of the k-center problem. For I and problem efficiently with a dominating set algorithm.
the minimum dominating set D in Gi one can prove [5], 2004. (poslano v recenzijo).
that |I| ≤ |D|. Notice also that the maximum edge weight [10] E. Minieka. The m-center problem. SIAM Rev.,
of G2i is at most twice the maximum edge weight of Gi . 12:138–139, 1970.

Thus, we can solve the k-center problem by solving series [11] P. B. Mirchandani and R. L. Francis, editors.
of dominating set problems or, alternatively, maximal in- Discrete Location Theory. John Wiley & Sons, New
dependent set problems. The later approach results in a York, 1998.