Об аппроксимационной сложности задачи о минимальном комитете

The minimal Committee combinatorial problem (MC) is studied. It’s know that this problem is $NP$-hard (see e.g. [1]). In this paper we show that unless $NP \not\subset T IME (m^{O{(\log\log m)}})$ there are no approximation algorithms for this problem with factor ($1-\varepsilon$) ln $m$ for every $\varepsilon > 0$ even when all sets used in it’s formulation are finite. To prove this estimate we reduce to it a SET COVER problem for which the same result is know [2].