9
$\begingroup$

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.

$\endgroup$

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.