Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem

Consider the Hitting Set problem where, for a given universe $\mathcal{X}=\{1,\mathrm{.}\mathrm{.}\mathrm{.},n\}$ and a collection of subsets ${\mathcal{S}}_1,\mathrm{.}\mathrm{.}\mathrm{.},{\mathcal{S}}_m$, one seeks to identify the smallest subset of $\mathcal{X}$ which has nonempty intersection with every element in the collection. We study a probabilistic formulation of this problem, where the underlying subsets are formed by including each element of the universe with probability $p$, independently of one another. For large enough values of $n$, we rigorously analyse the average case performance of Lovász’s celebrated greedy algorithm (Lovász, 1975) with respect to the chosen input distribution. In addition, we study integrality gaps between linear programming and integer programming solutions of the problem.