Paradigms for Optimization Problems - A Concise and Practical Introduction to Programming Algorithms in Java - page 218

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).