Maximize number of subsets

Question

Given a list of subsets $S_1, \ldots, S_n$ of the universal set $U = \{e_1,\ldots, e_m\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S_i$. In another words, $$\max_{S \subset U\\ |S| = k} \sum_{i = 1}^n \mathbb{1}_{S_i \subseteq S}$$ Where $\mathbb{1}$ is an indicator function.

For my application, $n, m \approx 10000$, $k = 16$, and $|S_i| = 3$. Thus the naive brute-force approach will not work. (I think this is an NP-hard problem in general if you allow $k$ to vary).

Question: Find algorithm that get closest to the optimal solution within reasonable time ( ex $O(n^2)$)

As an approximation algorithm, I have tried the following greedy algorithm, but I would like a solution that gets closer to the optimal solution. We will start with $S = \emptyset$ and add one element at a time to $S$. Take $U = \{e_1,\ldots, e_m\}$. Rank each element using the following. Define $H_{j,c}$ as number of sets $S_i$ such that $|S_i \setminus (S\cup \{e_j\}| = c$. i.e. $$H_{i,j} = \sum_{i = 1}^n \mathbb{1}_{|S_i \setminus (S\cup \{e_j\}| = c} $$

Add that element $e_j$ to $S$ which has the maximum ordered value $(H_{j,1}, H_{j,2}, \ldots, H_{j, m})$ as per the lexigraphical ordering. (Use $H_{j,1}$ as the main score, and use $H_{j,2}$ as a tie breaker and so forth).

Repeat until $|S| = k$.

PS.

1. I think I did a poor job of explaining the problem and my attempt at the problem. I would appreciate any edits to make this question clearer.
2. I am trying to use this problem, as a greedy approach to my previous question Graph partition that maximize the number of triangles within its parts. But I think this question is interesting as well.

Answer 1

I'm not sure how well it'll work, but the idea is simple:

1. Consider a continuous relaxation of the function
2. Run projected gradient descent

1.) First, consider a discrete case: let $x_i$ be $1$ if we pick an $i$-th element, and $0$ otherwise. The constraint is $\sum_i x_i \le k$. For each set $S_j$, we want to write a function which is $1$ when all $i \in S_j$ are picked, and $0$ otherwise. A natural choice is $g(S_j, x) = \prod_{i \in S_j} x_i$. Our objective is $f(x) = \sum_j g(S_j, x)$

Now, to make it continuous, let $x_i$ vary in the range $[0,1]$ - in other words, it represents a probability that we pick the $i$-th element. Now, $g(S_j, x)$ represents the probability that the set $S_j$ is chosen. The constraint $\sum_i x_i \le k$ and the objective $f$ are as before.

Therefore, the continuous relaxation is the following: \begin{align*} f(x) &= \sum_j \prod_{i \in S_j} x_i \to \max & s.t.\\ x_i &\in [0,1] \ \ \forall i \\ \sum_i x_i &\le k \\ \end{align*}

2.) The gradient has a relatively simple form: $$(\nabla f(x))'_{x_i} = \sum_{j\colon i \in S_j} \prod_{i' \in S_j \setminus \{i\}} x_{i'}$$

In other words, it's a sum of over terms containing $x_i$: product of all factors except $x_i$.

Since the problem is constrained, you need to run $projected$ gradient descent. I.e.

$$x^{(t+1)} \gets Proj(x^{(t)} - \gamma \nabla f(x^{(t)})),$$

where $Proj$ is a projection on the set $\{x | \sum_i x_i \le k \land x_i \in [0,1] \ \ \forall i\}$. It may be hard to find the exact projection, but you can use Alternating projection or, better, Dykstra's projection. For that purpose, we rewrite our constraint set as $$\{x| \sum_i x_i \le k\} \cap (\cap_i\{x| x_i \le 1\}) \cap (\cap_i\{x| x_i \ge 0\}).$$

Now, we can project at each set in turns. Note that projection on $\{x| x_i \le 1\}$ is trivial: when $x_i \le 1$, don't do anything, otherwise $x_i \gets 1$.

I'm not sure that the function is "good", and therefore I would try a smaller step size first. There are multiple optimizations that one can do, but I omit them here.

Answer 2

I can describe a solution that runs in linear time and is likely to give a solution that is close to optimal, if all of the sets $S_i$ are chosen uniformly at random, and only for the specific parameters you mentioned. The method is easy to describe; explaining why it is likely to be close to optimal is much hairier.

Algorithm

1. Pick two sets $S_{i_1},S_{i_2}$ that share two elements in common.

2. Pick $S_{i_3}$ that shares an element with $S_{i_2}$ and is different from $S_{i_1},S_{i_2}$.

3. Pick $S_{i_4}$ that shares an element with $S_{i_3}$ and is different from $S_{i_1},S_{i_2},S_{i_3}$.

4. Repeat until you have chosen $S_{i_8}$.

5. Output $S := S_{i_1} \cup \cdots \cup S_{i_8}$.

Running time

This can be implemented in $O(n)$ time. In preprocessing, you build up a hash table that maps $e_j$ to a list of all sets $S_i$ that contain $e_j$. This can be done by scanning through the sets and doing $3n$ inserts into the hash table. Also, build up a second hash table that maps the pair $(e_j,e_k)$ to the list of all sets $S_i$ that contain both $e_j$ and $e_k$. This too can be done by scanning through the sets and doing $6n$ inserts. Then, step 1 of the algorithm above can be implemented efficiently using the second hash table, and each subsequent step can be implemented efficiently using the first hash table. When the algorithm says "pick", you can choose randomly from among all choices. If you ever get stuck (there are no valid choices), you can start over (this is unlikely to happen).

Analysis of optimality

Why does this work? The reason involves some more combinatorics, and relies heavily on the assumption that the $S_i$'s are random.

In particular, under this assumption, I believe it is overwhelmingly likely that the optimal solution covers 9 subsets. My estimates suggest that there is something like a $2/10^6$ chance that there exists a solution that covers 10 subsets; while the chance that there exists a solution that covers 9 subsets is nearly 1. So, we can focus on how to cover 9 subsets.

I also claim that the algorithm above is likely to give a solution that covers 8 subsets. In particular, by construction, if it terminates, it outputs a solution $S$ that covers 8 subsets, namely, it covers $S_{i_1},\dots,S_{i_8}$. Also, by construction, $S$ has $3 \times 8-2-6=16$ variables, as $S_{i_2}$ has two variables in common with $S_{i_1}$, and each subsequent set has one variable in common with the previous sets. Doing some combinatorics, it is overwhelmingly likely that there will exist some pair of sets $S_{i_1},S_{i_2}$ that have two variables in common (in fact we expect about 18 of them on average); and for each, set $S_{i_j}$, it is overwhelmingly likely that there will be another set we can choose for $S_{i_{j+1}}$ that has one variable in common with it (we expect about 8 or 9 of them on average). So the algorithm is overwhelmingly likely to succeed.

Thus, this gives an efficient algorithm that outputs a solution that covers 8 subsets; and the optimal solution likely covers 9 subsets; so this is quite close to optimal.

I hope I got all the combinatorics right... I recommend you test this to see if it actually works out as I am expecting.

Caveats

As a reminder, this only works if the sets are chosen randomly. If they have some structure, it might fail badly. Also, it is very specific to the particular parameter settings you have listed (especially, $n \approx m$).