Java Reference
In-Depth Information
Exercise 9.4 (Discriminating set problem)
X
,
R
|X |
=
n
elements
X
1
, ..., X
n
and
|R|
=
m
Given a range space (
)of
subsets
R
1
, ..., R
m
, we would like to find a discriminating set
X
⊆
X
=
R
j
∩X
.
-
Prove that finding a minimum size discriminating set
=
jR
i
∩X
such that
∀
i, j, i
X
amounts
to solving a hitting set problem for the set of pairwise symmetric
differences
R
i
R
i
. Design a greedy algorithm
for finding a not too large discriminating set. Deduce that memory
requirement is quadratic.
R
j
=
R
i
\
R
j
∪
R
j
\
-
Instead of explicitly computing the full set of symmetric differences of
ranges, design an algorithm that solves the hitting set problem using
only linear memory (but more time).
Search WWH ::
Custom Search