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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.