Information centre allocation
| Date | 01 June 1994 |
| DOI | https://doi.org/10.1108/eb045324 |
| Published date | 01 June 1994 |
| Pages | 361-365 |
| Author | J. Bar‐Ilan,G. Kortsarz,D. Peleg |
| Subject Matter | Information & knowledge management,Library & information science |
Article
Information centre
allocation
J.
Bar-Ilan
School
of
Library,
Archive and Information Science,
The
Hebrew University of Jerusalem,
Jerusalem
91904,
Israel
E-mail:
judit@shum.cc.huji.ac.il
G. Kortsarz and D. Peleg
Department
of Applied Mathematics and Computer
Science,
The Weizmann Institute,
Rehovot,
Israel
Abstract: A large number of potential sites are given and
we have
to choose k sites in order to set up information
centres,
where
each centre is able to serve a limited number
of clients. The price a client pays for accessing a centre is
proportional to the distance between the client and the
centre. This problem belongs to a class of problems for
which
most theoretical computer scientists believe that there
is
no fast algorithm for finding
an
optimal solution. We
therefore
look for algorithms that produce an approximate
solution.
In this paper we present a fast algorithm that
chooses
k sites and assigns the clients to the centres
in
such
a
way
that the maximum price a client pays is at most nine
times
the maximum price in an optimal solution. This
algorithm
works under the assumption that the number of
chosen
sites
is
small in comparison to
the
number of
possible
sites.
1.
Introduction
Consider
the
following
problem:
there are p potential sites for
setting up information centres. The budget allows k such cen-
tres to be set
up.
There is
a
given set of clients who wish to use
these
centres.
Clients have
to
pay for accessing an information
centre. We assume that the price they pay is proportional to
the distance between the client and the centre. We further as-
sume that there is a bound,
t,
on the number of clients a centre
can serve and that each client is assigned to a fixed centre.
Our aim is to choose k sites and to assign each client to a
centre in such a way that no centre serves more than t clients,
and the maximum price a client pays for accessing 'his' infor-
mation centre is minimal. We call this maximum price the
price of the solution.
It turns
out that this is one of the problems theoretical com-
puter scientists consider hard (an NP-hard problem). This
roughly means that there is no known algorithm that is much
better than checking every possible solution and then choos-
ing the cheapest one. For theoretical reasons, it is highly un-
likely that an efficient algorithm solves any of the NP-hard
problems. An exhaustive search is unfeasible when the num-
ber of potential sites is large.
Therefore we try to approximate the solution, i.e. to give a
fast approximation algorithm that finds
a
solution which
is
not
'much worse' than the optimal one. By this we mean that our
algorithm chooses k sites and a legal assignment of the clients
to the centres in such a way that the price of the solution is at
most g times the price of the optimal one. We call g the ratio
or guarantee of the approximation algorithm.
We present a fast approximation algorithm with guarantee
9 to this problem, under the technical assumption that the
number of centres is small compared to the number of sites
(more precisely k
is at
most a constant
times
loglog2(p)). With-
out this assumption, and if it is assumed that there is only one
kind of node (unlike here, where we have clients and sites),
there is an approximation algorithm with ratio 10 (see Bar-
Ilan et
al.
(1993)). As
a
building stone in our algorithm we use
an approximation algorithm with guarantee 3 that solves the
problem, in case there is no bound on the number of clients
that a centre can serve (see Hochbaum & Shmoys (1986)).
In the next section we present an exact algorithm for an
optimal assignment of the clients to the centres, once the cen-
tres are chosen. Next we describe Hochbaum & Shmoys' ap-
proximation algorithm for the unbounded case (Hochbaum &
Shmoys 1986). Finally, we use these two ingredients to pro-
duce an approximation algorithm for the bounded case.
2.
Assigning clients to centres
In this section we assume that the centres have already been
selected. Clients have to be assigned to the centres in such a
way that each centre serves at most
t
clients. Our aim
is
to pick
such an assignment
in
which the maximum distance of
a
client
to its centre is minimal. We present this algorithm first be-
cause it is used as a building block in our algorithm for select-
ing the centres.
We view the assignment problem as a graph theoretic
problem. A graph G=(V, E)
is
given where V
is
the set of nodes
and Ε is the set of
edges.
The set V consists of two
sets:
the
set of clients and the set of chosen centres (recall that the
size of is k
).
There is an edge between every pair of nodes in
the graph. Each edge e between two nodes v1 and v2 has a
weight
w(e),
where w(e) is the distance between
v1
and v2. For
The Electronic Library, Vol. 12, No. 6, December 1994 361
To continue reading
Request your trial