Wikipedia says that

Set covering is equivalent to the hitting set problem

What problem is to the set packing problem, as the hitting set problem is to the set cover problem?

Is it that given the ground set $U$, and a collection of its subsets, $S \subseteq \mathcal P(U)$, find a $H \subseteq U$, so that $|H \cap S_i | \leq 1, \forall S_i \in S$, and maximize $|H|$.

What is the name of a set $H$ that satisfies $|H \cap S_i | \leq 1, \forall S_i \in S$ in this problem? I.e. the counter part of a hitting set in the hitting set problem?



1 Answer 1


Let $E$ be indicator matrix $e_{ij}=[u_j\in S_i]$ and $w\geq 0$ be boolean vector. What you have written is $Ew\leq 1$ where $(1,w)$ is being maximized. If we relax this to linear programming and get respective dual $E^tv\geq 1,\, v\geq 0$ where $(1,v)$ is minimized. Latter problem under constraints $u\in\{0,1\}^m$ would be Set Cover problem. To get respective Hitting Set consider new sets $S'_j=\{S_i:u_j\in S_i,\,i=1,\ldots,m\}$ and new ground set $U'=\{S_i:i=1,\ldots,m\}.$ The Set Cover reduces to Hitting Set for sets $\{S'_j\}$ over ground set $U'.$ So Set Packing and Set Cover are dual in some way. But their optimal values do not coincide but they do coincide for their convex relaxations. More on this topic see e.g. in Wlliamson

You could also consider $H$ as being maximum independent families of sets $S_i.$ Let $F_h=\bigcup\limits_{h\in S_i}S_i,\,h\in H.$ These families are non-intersecting. Set Packing optimum is the lower bound for Set Cover.

As for $H$ interpretation. I suppose $S_i$ represents class of some useful things to take. Overall utility is maximized while the only one thing can be taken from each class.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.