# Lower bound for optimal solution for 3-hitting set approximation problem?

I want to come up with a 3-approximation ratio for the hitting set problem:

• There exist subsets $$F_i$$ of $$F$$ for $$i=1,...,k$$ of some numbers of universe $$U=\{1,...,n\}$$ with $$∣F_i∣=3$$ e.g. $$F_1=\{1,2,3\}$$
• Find the minimum hitting set $$S$$, that is a set for which $$S\cap F_i \not = \emptyset$$ for each $$i=1,...,k$$

My greedy algorithm always picks, while there still exists a set $$F_i$$ not hit, an arbitrary set maximizing the number of unhit sets (which is always 3) to the solution set $$S$$ and removes every hit set from $$F$$.

Now, my proof follows the idea, that in any iteration I always pick a set of size 3. If a set is unhit, then it always will be of size 3. But my problem is finding a lower bound for the optimal solution, say $$S^*$$. Is it sufficient enough to say, that whenever greedy adds a set of size 3, the optimal solution would have picked at most 1 out of all elements? I am missing how to connect the inequalities of $$S \leq 3*S^*$$...

• See standard approximation algorithms for Set Cover and its variants. This is not a research level question. Feb 10 at 16:37