Packing sets to maximize overlap

Question

We are given a set of $m$ elements $\{e_1,...,e_m\}$ that form our universe $\mathcal{U}$. Each element of our universe is further associated with a positive weight $w(e_j)$ with $j\in \{1,...m\}$. We are further given a collection $S=\{S_1,...S_n\}$ of subsets of $\mathcal{U}$ whose union equals the universe. The intersection of any two sets in $S$ may be non-empty (i.e. subsets may overlap with each other).

Furthermore,

1) we are given an infinite number of configurations; each configuration can host up to $k$ subsets from $S$. There is no cost for using a configuration.

2) When assigning 2 or more subsets to one configuration and there is an overlap between the sets (i.e. an element is part of more than one set) we pay the weight of that element only once. Obviously, there can be no overlap between subsets when considering different configurations.

Objective:

we want to assign each subset of $S$ to exactly one configuration in such a way that the weighted sum of the elements over all configurations is minimized. Consider the following example:

$\mathcal{U}=\{a,b,c,d,e,f,g\}$,

$w(a)=2$

$w(b)=2$

$w(c)=3$

$w(d)=4$

$w(e)=1$

$w(f)=2$

$w(g)=2$

$S=\{S_1, S_2, S_3\},$

$S_1=\{a,b,c\}, S_2=\{c,d,e\}, S_2=\{e,f,g\}$

$k=2$

In this case, since $k<|S|$, it is obvious that more than one configurations are needed. Moreover, $S_1$ and $S_2$ should be packed together in the same configuration because of their heavy overlap ($S_1 \cap S_2$ gives the biggest overlap in our example - we pay 3 less cost units). So, the total cost of such an assignment is 12+5=17 and 2 configurations are needed.

Any ideas on how to prove that the problem is indeed intractable? Any ideas on how to calculate a good bound on the number of configurations that are needed?

The unweighted version (when the weights of the elements are all 1) is also very interesting to me. However, I did not manage to find something so far in the literature also for this problem.

Thank you!

Answer 1

When $k=1$, the problem is trivial: the optimal solution is to put each set in its own configuration.

When $k=2$, the problem can be solved in polynomial time using graph matching. Build a complete undirected graph with one vertex per set. The cost of the edge $(S_i,S_j)$ is the cost of putting $S$ and $T$ together in the same configuration (i.e., the weight of $S_i \cup S_j$). Now the optimal solution to your problem is given by the minimum-cost perfect matching in this graph. That matching can be computed in polynomial time using standard algorithms.

When $k=3$, the problem is NP-hard. In fact, it is NP-hard to determine whether a graph can be covered by a disjoint union of cycles of length $\le 3$ (i.e., whether you can find a set of cycles, where each cycle has length 2 or 3, where no two cycles have any vertex in common, and where every vertex appears in one of these cycles). This implies that your problem is intractible when $k\ge 3$.

The proof of the hardness result I alluded to can be found in Section 3 of the following paper:

Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. David J Abraham, Avrim Blum, Tuomas Sandholm. EC 2007.

That said, not all hope is lost. There are techniques available for finding a solution that will be close to optimal, using integer linear programming. For instance, you can express your problem as an instance of integer linear programming and then apply an off-the-shelf ILP solver. See the paper above for some more sophisticated techniques that might be applicable in your situation as well.