On the minimum hitting set of bundles problem (Q1035686)

An input of the minimum hitting set of bundles problem is an set \(\mathcal E=\{e_1,e_2,\dots,e_n\}\) of \(n\) elements with non negative costs \(c_i\) for \(i=1,2,\dots,n\) and a collection \(\{S_1,S_2,\dots,S_m\}\) where \(S_i\) is a set of subsets of \(\mathcal E\). The aim is to find a solution with minimium total cost where a solution is a subset \(\mathcal E'\subseteq \mathcal E\) such that for every \(i=1,2,\dots,m\) there exists \(b\in S_i\) with \(b\subseteq \mathcal E'\) and the total cost is \(\sum \{c_i\mid e_i\in \mathcal E'\}\). There is given \(N(1-(1-\frac 1N)^M)\)-approximation polynomial time algorithm where \( N\) is the maximum number of subsets of \(\mathcal E\) per set and \(M\) is the maximum number of sets in which an element can appear. The scheme of algorithm is classical but the approximation ratio is the best one. Relation of this algorithm to similar problems is discussed.