# Complexity of Finding Optimal Synergistic Set Packings

Motivation: While developing tools for fast execution of machine learning workflows, we realized that many workflows require intermediate results -- sometimes we should cache these results, and sometimes we should recompute them from scratch.

We were able to reduce the problem of determining the optimal set of intermediate results to cache to the following very natural problem, which I call synergistic set-packing.

Problem: We are given a universe of $m>0$ elements $U = \{e_1, e_2, \ldots, e_m\}$, as well as a function $c : U\rightarrow \mathbb{Z}^+$ which maps each element to some positive integral cost. We are furthermore given a collection $\mathcal{C}$ containing $n>0$ nonempty subsets of $U$; $\mathcal{C} = \{S_1, S_2, \ldots, S_n\}$. Finally, we are also given a function $p : \mathcal{C} \rightarrow \mathbb{Z}^+$ which maps each $S_i$ to some positive payoff.

Our goal is to choose $X \subseteq U$ that maximizes the following benefit function of payoff - cost: $$\left(\sum_{S_i\in\mathcal{C} \text{ with } S_i\subseteq X}p(S_i)\right) - \left(\sum_{e_j\in X} c(e_j)\right)$$

That is, if we pick all of the elements for some $S_i \in \mathcal{C}$, we get a payoff of $p(S_i)$, but we must pay for all of the elements in $S_i$ to get this payoff.

Approaches: At first glance, this problem seems pretty similar to the (somewhat obscure) NP-hard minimum K-union problem (1), where our goal is to pick the $k$ sets whose union cover the fewest elements (in our problem, in the case of unit costs / payoffs, we would try to pick the $k$ elements that hit the fewest number of sets, and then include the rest of the $m-k$ in $X$, but the analogy does not quite work since there is no requirement that we choose $X$ to have at most $m-k$ elements).

Any help with characterizing this problem's complexity is of course much appreciated!

Example: I will put the cost/payoff next to each item, after a colon. Suppose $U$ is given by (along with costs) $\{e_1: 2, e_2: 2, e_3: 1\}$, and in our collection we have: $$S_1 = \{e_1, e_2\} : 1$$ $$S_2 = \{e_2, e_3\} : 4$$

Then in this case we would pick $X = \{e_2, e_3\}$, for a total cost of 3 and a payoff of 4, for a net benefit of 1.

(1) Staal A. Vinterbo (2002). A Note on the Hardness of the k-Ambiguity Problem. DSG Technical Report 2002-006.

For your case, you would have one project for each set $S_i$, and also one project for each $e_j$. Each $e_j$ project has no dependencies, and each $S_i$ will depend on the $e_j$ in $S_i$. The benefit of $S_i$ is its payoff, and the 'benefit' of each $e_j$ is the negative of its cost. You can see that reasonable ways of selecting projects correspond to all the ways of picking solutions to your problem, and the objective values are the same on either side of the correspondence.