# Examples for a kind of “set family hitting” problem

Given a ground set, say $$[n]=\{1,2,\dots,n\}$$, and a collection of subset families $$\mathcal F_i\subseteq 2^{[n]}$$, $$i=1,2,\dots,m$$, I want to select $$m$$ sets $$B_i\in\mathcal F_i$$ such that the cardinality of the union $$B_1\cup B_2\cup\dots\cup B_m$$ is minimized. In other words, I want to hit each of the families $$\mathcal F_i$$ touching as few elements of the ground set as possible.

From this answer over at cstheory, I learnt that the general problem is very hard to approximate (reduction from the Min-Rep problem introduced in Kortsarz, Guy. "On the hardness of approximating spanners." Algorithmica 30(2001): 432-450).

On the other hand, the following scheduling problem can be interpreted as a very very special case which can be solved efficiently: We want to schedule a set of jobs indexed by $$i$$ (given by earliest start time $$r_i$$, latest completion time $$d_i$$ and processing time $$p_i$$) on a single machine of infinite capacity, and the objective is to minimize the total busy time of the machine. In this setting, the family $$\mathcal F_i$$ would just be the set of intervals $$\{[r_i,r_i+p_i-1],[r_i+1,r_i+p_i],\dots,[d_i-p_i+1,d_i]\}$$ (Rohit Khandekar, Baruch Schieber, Hadas Shachnai, and Tami Tamir. “Real-time scheduling to minimize machine busy times”. Journal of Scheduling 18 (2015), p. 561-573, doi:10.1007/s10951-014-0411-z)

I'd be interested to learn about any other special cases of the problem with structured families $$\mathcal F_i$$ which may have been considered in an OR context.