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^*$...

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.