Questions tagged [hitting-set]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1 votes
0 answers

Lower bound for optimal solution for 3-hitting set approximation problem?

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,...
FishyK's user avatar
  • 1
1 vote
1 answer

Balanced set coloring

Let $\{S_1, S_2, ..., S_m\}$ be a collection of subsets of some universe $U$, where each $S_i$ has even size (so does $U$). We want to color the elements of $U$, either red or blue, such that each $...
Arnaud Casteigts's user avatar