Java Reference
In-Depth Information
(a)
(b)
Figure 9.4
Set cover problem for urban radio network planning of mobile
phones: (a) Covering of 99 base transceiver stations, and (b) covering using
only 19 base stations. Here, some redundant areas covered more than four
times
algorithm does not yield an optimal solution but guarantees an approximation
solution. Let
c
∗
=
I
∗
|
be the size of any optimal solution,
2
and
c
=
denote
the size of the solution reported by this greedy strategy. Then we have the
following bounds:
|
|
I
G
|
c
∗
≤
c
∗
(1 + log
n
)
.
c
G
≤
To implement the greedy algorithm for the set cover problem, we first need
to organize the data-structures for coding the range space (
X
,
S
). We choose
to represent subsets of
using a
boolean incidence matrix B
. Matrix element
B
[
i, j
]issetto
true
if and only if element
X
j
belongs to set
S
i
. The ranges are
therefore encoded in the matrix rows while columns depict element membership
in respective ranges. The basic code for creating and initializing an instance of
a set cover problem is given in the following class
SetCover
.
X
Program 9.10
Initializing a set cover problem
class
SetCover
int
nbelements ;
int
nbsubsets ;
boolean
[ ] [ ] incidenceMatrix ;
SetCover(
int
nn ,
int
mm)
this
. nbelements=nn;
this
. nbsubsets=mm ;
incidenceMatrix=
new boolean
[ nbsubsets ][ nbelements ];
2
Note that several solutions of same size may exist.
Search WWH ::
Custom Search