Packing sets to maximize overlap

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!

• I don't understand the problem you're trying to solve. What objects are weighted? What does it mean to minimize "in multiple configurations"? When $|S|=10$ and $k=4$, why are there three configurations? Whatever all those things mean, isn't the problem exactly the classical set cover problem when you set all the weights equal to 1 and have only one configuration? If set cover really is a special case, and your problem is still in NP (which should be trivial to prove), then your problem is automatically NP-complete. – David Richerby Mar 28 '16 at 5:38
• Please give an example. As stated, your problem is hard to understand. Also, as David mentions, perhaps the best you can do is use approximation algorithms or heuristics. – Yuval Filmus Mar 28 '16 at 8:15
• Thank you for your answers. I tried to come up with a better description of my problem. Hope that the new description is much clearer. – Christos AMS Mar 28 '16 at 12:59
• – Kaveh Apr 30 '16 at 0:53

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