Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem

Gabriel Arpino, Daniil Dmitriev, Nicolo Grometto

Consider the Hitting Set problem where, for a given universe $\mathcal{X}=\left\{1,...,n\right\}$ and a collection of subsets ${\mathcal{S}}_1,...,{\mathcal{S}}_m$, one seeks…