1
$\begingroup$

My problem is very similar to the one posted here. Instead of finding one set covering the maximum of subsets, I need to find the minimal number of sets to cover all subsets.

I have $U = \{1, 2, ..., 1000\}$ and $S \subseteq \{A \subset U |\space|A| \leq 15\} $. I know that $|S| < 1000$. I need to find a minimal number of sets of fixed size (e.g. 25) such that each set in $S$ is a subset of at least one of the fixed size sets.

It is not necessary that I have the minimum number of sets, a minimal number is sufficient.

I guess the problem can be split in those two steps:

  1. Remove all sets that are subsets of other sets
  2. Find minimal number of sets (of fixed size) that contain all given sets

It doesn't make the problem easier. How would I go about it? What are good algorithms for the two steps?

$\endgroup$
  • $\begingroup$ Nice, but isn't this pure math? Where do computers enter the picture? $\endgroup$ – greybeard Apr 3 '15 at 10:17
  • $\begingroup$ @graybeard It's a computational problem. Note that $S$ doesn't consist of all subsets of size at most $15$. $\endgroup$ – Yuval Filmus Apr 3 '15 at 11:03
  • 1
    $\begingroup$ This is a specific case of set cover. Are you looking for a reasonable heuristic? In that case, do you know anything more about $S$? Is this for a programming competition? $\endgroup$ – Yuval Filmus Apr 3 '15 at 11:05
  • $\begingroup$ What's the difference between "minimum number of sets" vs "a minimal number"? Does this mean you are OK with an approximation algorithm or a non-optimal solution? $\endgroup$ – D.W. Apr 3 '15 at 11:13
  • $\begingroup$ @Yuval No, it is not for a programming competition. It is for a project of mine. I am OK with an approximation. It does not have to be the minimum number, but a number that is close to the minimum. $\endgroup$ – meow Apr 3 '15 at 11:19
1
$\begingroup$

If the sets are chosen randomly, then for the parameters you chose, the problem can be solved efficiently. In particular, the following trivial algorithm will output the correct answer with high probability: take each set of $S$, pad it by adding 10 random elements, and output the result (all sets of $S$, padded).

This might sound wasteful, but for the parameters you mentioned, if the sets are chosen randomly, it's unlikely you can do better. You can only do better if there exist two sets $s,t \in S$ that can be covered by a 25-element set, i.e., such that $|s \cup t| \le 25$. This happens only if $s,t$ have at least 5 elements in common (i.e., $|s \cap t| \ge 5$).

Now when $s,t$ are chosen uniformly at random from all possible sets of size 15, the probability that they have two elements at random is very small. It is approximately ${15 \choose 5}^2/1000^5 \approx 9 \times 10^{-9}$. Also, there are ${1000 \choose 2}^2$ possible pairs $s,t$, so by a union bound, the probability that there exist two such sets $s,t$ is about $0.0045$. This means there is only a small probability that you can cover two sets from $S$ by a single set of size 25, if the sets of $S$ are chosen randomly.

In general, for your problem, one approach would be to find all pairs of sets $s,t \in S$ that overlap in at least 5 elements. Build a graph where $S$ is the vertex set and you add an edge between $s,t$ if $|s \cap t| \ge 5$. Find a maximum matching in this graph. Then you can use this to build a set of 25-size sets (one 25-size set per edge in the matching, plus one set per vertex not touched by the matching). However, if the sets are generated randomly, this is unnecessary as it is unlikely to find any pair of sets that overlap in at least 5 elements.

Anyway, if the sets are chosen uniformly at random, the problem is uninteresting for the parameters you gave. If the sets aren't chosen uniformly at random and have some structure, I recommend that you edit the question to describe this structure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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