Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem

Consider the Hitting Set problem where, for a given universe X = {1, . . ., n} and a collection of subsets S1, . . ., Sm, one seeks to identify the smallest subset of X which has a 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 independently with probability p. We rigorously analyze integrality gaps between linear programming and integer programming solutions to the problem. In particular, we prove the absence of an integrality gap in the sparse regime mp ≲ log n and the presence of a non-vanishing integrality gap in the dense regime mp ≫ log n. Moreover, for large enough values of n, we look at the performance of Lovász’s celebrated Greedy algorithm [12] with respect to the chosen input distribution, and prove that it finds optimal solutions up to multiplicative constants. This highlights separation of Greedy performance between average-case and worst-case settings.