1
$\begingroup$

I have a set $S$ of $N$ elements, and a set $\Sigma$ of $N$ subsets of $S$: $\sigma_0, \ldots, \sigma_{N - 1} \subset S$, each with $W \ll N$ elements. Subsets can overlap partially or totally.

For a given $K < N$ (but $K \gg W$), I want to determine the subset $X_K \subset N$ so that:

  • $X_K$ has $K$ elements.
  • $X_K$ includes the largest possible amount of subsets among $\sigma_0, \ldots, \sigma_{N -1}$.

Example:

$S = \{A, B, C, D, E\}$, $W = 3$

$\{\sigma_0, \ldots, \sigma_4\}= \{\{A, B, C\}, \{A, B, C\}, \{B, C, D\}, \{A, B, E\}, \{A, B, D\}\}$

$X_4 = \{A, B, C, D\}$ (as it includes $\sigma_0, \sigma_1, \sigma_2$ and $\sigma_4$)

What is the best algorithm to find $X_K$?

$\endgroup$
  • 2
    $\begingroup$ It's NP-hard. You might be able to adapt heuristics or approximation algorithms for set cover or maximum coverage. $\endgroup$ – D.W. Jan 25 '17 at 0:11
1
$\begingroup$

I had the same problem a few days ago and I used the following heuristic to do it. According to my first impression it seems to work.

My specific use case was to determine a strategy in which sequence I should convert function implementations from one programming language into another so that we can execute as many test runs with as little effort as possible (in this case the set of functions is $S$ and the test runs are $\Sigma$ and our goal is to cover as many $\sigma \in \Sigma$ as possible with as few elements from $S$ as possible).

Example Data

So let's setup some example data. We have five sets $\sigma$ with different elements inside.

$$ \sigma_1 = \{s_1, s_3, s_4\} \\ \sigma_2 = \{s_1, s_5, s_6\} \\ \sigma_3 = \{s_1, s_3 \} \\ \sigma_4 = \{s_1, s_3, s_4, s_5, s_6\} \\ \sigma_5 = \{s_1, s_2, s_3, s_6\} $$

My Current Approach

I give each $s_j$ a rating based on the total number of time it exists. Then I check how many elements each $\sigma$ contains. I will then calculate the division between these two numbers and select the $\sigma$ with the highest rating as first winner.

In my opinion this should give me the quick win sets first. I will get at least one set covered and I try to trade-off between trying to get the smallest set first, and trying to select the $s$ that are used the most (i.e. with which I could probably cover the most $\sigma$).

Let me explain this approach on the example above. If we count the number of occurrences for each $s$, we get:

$$ \text{Usages}(s_1) = 5 \\ \text{Usages}(s_2) = 1 \\ \text{Usages}(s_3) = 4 \\ \text{Usages}(s_4) = 2 \\ \text{Usages}(s_5) = 2 \\ \text{Usages}(s_6) = 3 $$

If we use these and the number of elements in each $\sigma$ we get the following ratings:

$$ \text{Rating}(\sigma_1) = \frac{\text{Usages}(s_1) + \text{Usages}(s_3) + \text{Usages}(s_4)}{3} = \frac{5 + 4 + 2}{3} = \frac{11}{3} = 3.67 \\ \text{Rating}(\sigma_2) = \frac{5 + 2 + 3}{3} = \frac{10}{3} = 3.33 \\ \text{Rating}(\sigma_3) = \frac{5 + 4}{2} = \frac{9}{2} = 4.5 \\ \text{Rating}(\sigma_4) = \frac{5 + 4 + 2 + 2 + 3}{5} = \frac{16}{5} = 3.2 \\ \text{Rating}(\sigma_5) = \frac{5 + 1 + 4 + 3}{4} = \frac{13}{4} = 3.25 $$

In this case, I would add the elements $\{s_1, s_3\}$ to my set $X_k$ first.

For the next iteration I would delete $\sigma_3$ from the candidates and repeat the process.

Related Problems

I think that is problem is closely related to the set cover problem. However, it is different and I did not find a way to convert my problem into a set coverage problem. It also was different to any other algorithm I found in the area of set cover problem (e.g. set packing, dominating set, maximum coverage problem). Maximum coverage problem seems to come very close, but it is again a bit different.

$\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.