<p>I believe it's NP-hard, by a reduction from <a href="https://www.nada.kth.se/~viggo/wwwcompendium/node95.html" rel="nofollow">min-balanced cut</a>.  Given a graph $G=(V,E)$ and integer $\ell$, min-balanced cut asks whether there is a cut that is balanced (has $|V|/2$ vertices on each side), and cuts at most $\ell$ edges.  Given $G$ and $\ell$, construct the following instance of your problem.  For each vertex $v$, create a set $S_v$ containing the edges incident to $v$.  Take $k=|V|/2$.  Then the (minimal) $k$-good partitions are partitions of the sets into two equal-size groups, corresponding to the balanced cuts of $G$, and your (unweighted) cost for such a solution equals $|E|$ plus the number of edges cut.  Unless I'm mistaken :-).</p>

<p>EDIT: Similarly you can reduce the following problem to yours: given a graph $G=(V,E)$ and integer $\ell$, color the vertices of $G$ so that each color class has at most $k$ vertices, minimizing the number of edges whose two endpoints have the same color.  (The reduction: make a set $S_v$ for each vertex $v\in V$, containing the pairs $\{v,w\}$ not in $E$.)</p>

CC BY-SA 3.0
2016-04-01T03:30:53.267Z
2016-04-02T05:53:57.787Z
2016-04-02T05:53:57.787Z
Neal Young
<p>For a set of sets $A$, let $\cup A := \cup_{S \in A} S$.</p>

<p>Consider the following problem:</p>

<p><strong>Input</strong>: </p>

<ul>
<li>a list of $m$ weights $w = (w_1, \ldots, w_m)$,</li>
<li>a list of $n$ distinct subsets $T = (S_1, \ldots, S_n)$ such that $\bigcup_{S\in T} S = [m]$,</li>
<li>an integer $k$.</li>
</ul>

<p>Let $P$ be a partition of $T$. 
We say $P$ is a <em>$k$-good partition</em> when
the size of each part is at most $k$:
$\forall p \in P \ |p| \leq k$.
The cost of $P$ is defined as 
the sum of weight of items counted once for each part they appear in, i.e.
$$cost(P) := \sum_{p\in P} \ \sum_{x\in \cup p} w_x $$</p>

<p><strong>Output</strong>: a $k$-good partition of $P$ of $T$ minimizing $cost(P)$.</p>

<blockquote>
  <p>What is the complexity of this problem?<br>
  Is it NP-hard or is there a polynomial-time algorithm?</p>
</blockquote>

<hr>

<p><strong>Example</strong>:<br>
$m = 7$, $w=(2,2,3,4,1,2,2)$,<br>
$n = 3$, $T=(S_1=\{1,2,3\}, S_2=\{3,4,5\}, S_3=\{5,6,7\})$<br>
$k=2$</p>

<p>In this case, since $k&lt;|T|$, 
it is obvious that more than one partition is 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 optimal $P$ is $\{S_1, S_2\}, \{S_3\}$ with the total cost 12+5=17.</p>

<hr>

<p>The unweighted version (when the weights of the elements are all 1) 
is also very interesting to me. </p>

CC BY-SA 3.0
2016-03-28T06:37:43.473Z
An easy statement about the complexity is to reduce from Weighted Set Cover by simply setting $k=|S|$.
chazisop
CC BY-SA 3.0
2016-03-28T11:07:49.383Z
If I understand your question correctly, you're asking for an algorithm to solve the *weighted set cover problem* with bounded size, $k$. If you solve the normal *weighted set cover problem* and find that the minimum cover $C$ requires size $k'$, then don't you simply use $C$ if $k' \leq k$ and declare *no solution* otherwise?
Lawrence
CC BY-SA 3.0
2016-03-28T13:01:17.677Z
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
CC BY-SA 3.0
2016-03-28T13:58:31.303Z
My understanding is as follows. You have $S = \{S_1, S_2, ... S_m\}$. A configuration is a subset of $S$ with size $\leq k$. The cost of a configuration $C$ is $\sum_{x \in \bigcup C} w(x)$. You want to find a collection of $\leq |U|$ configurations minimizing $\sum_i cost(C_i)$ subject to $\bigcup \bigcup_i C_i = U$.  If my understanding is correct, then setting $k=1$ and $w(x)=1$ everywhere means that your cost will be exactly $|U|$ iff the system has an exact cover, doesn't it? It shouldn't get any easier for larger $k$, but that takes an argument that won't fit in the 3 characters left.
Yonatan N
CC BY-SA 3.0
2016-03-28T14:13:43.157Z
Hi Yonatan. Obviously, any subset should be part of exactly one configuration. Setting $k=1$ and  $w(x)=1$ everywhere means that the cost may be larger than $|U|$. This is because there may be overlaps between the sets in $S$. What you claim is true - the total cost will be equal to $|U|$ iff every element is included in exactly one subset.
Christos AMS
CC BY-SA 3.0
2016-03-28T14:36:48.687Z
Oh. That second sentence wasn't clear from the initial post, I think. In that case, my comment is not relevant.
Yonatan N
CC BY-SA 3.0
2016-03-28T14:49:39.237Z
No, I think it is. Consider the objective function of such a problem. It is never beneficial to select this subset more than 1 time (in the same or different configurations).
Christos AMS
CC BY-SA 3.0
2016-03-28T15:20:48.783Z
Thanks Yonatan for your previous comment. I just updated the description of the problem.
Christos AMS
CC BY-SA 3.0
2016-03-29T02:39:17.623Z
Even after the clarifying remarks, I don't understand the statement of the problem.
Neal Young
CC BY-SA 3.0
2016-03-29T16:45:44.040Z
There is one more update in the description!
Christos AMS
CC BY-SA 3.0
2016-03-30T03:53:54.037Z
You don't define what is a configuration and it doesn't seem that configurations are given as input. You should edit the question and clarify exactly what is the input for the problem. Then you should clarify what is the output (e.g. is it a partition of S which minimizes the cost of the partition where the cost of a partition is the sum of cost of intersections of members of S in each part?)
Kaveh
CC BY-SA 3.0
2016-03-30T04:35:52.383Z
I edited the question for clarification based on my understanding, please check the edited version and feel free to edit further.
Kaveh
CC BY-SA 3.0
2016-04-30T00:53:06.453Z
[cross posted](http://cs.stackexchange.com/q/55037/) on [cs.se].
Kaveh
<cc.complexity-theory><ds.algorithms><np-hardness><packing>
Packing sets to maximize overlap
Christos AMS
# Packing sets to maximize overlap

(Asked by: username_0 on 2016-03-28)

For a set of sets $A$, let $\cup A := \cup\_{S \in A} S$.

Consider the following problem:

**Input**:

* a list of $m$ weights $w = (w\_1, \ldots, w\_m)$,
* a list of $n$ distinct subsets $T = (S\_1, \ldots, S\_n)$ such that $\bigcup\_{S\in T} S = [m]$,
* an integer $k$.

Let $P$ be a partition of $T$.
We say $P$ is a *$k$-good partition* when
the size of each part is at most $k$:
$\forall p \in P \ |p| \leq k$.
The cost of $P$ is defined as
the sum of weight of items counted once for each part they appear in, i.e.
$$cost(P) := \sum\_{p\in P} \ \sum\_{x\in \cup p} w\_x $$

**Output**: a $k$-good partition of $P$ of $T$ minimizing $cost(P)$.

> What is the complexity of this problem?  
> Is it NP-hard or is there a polynomial-time algorithm?

---

**Example**:  
$m = 7$, $w=(2,2,3,4,1,2,2)$,  
$n = 3$, $T=(S\_1=\{1,2,3\}, S\_2=\{3,4,5\}, S\_3=\{5,6,7\})$  
$k=2$

In this case, since $k<|T|$,
it is obvious that more than one partition is 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 optimal $P$ is $\{S\_1, S\_2\}, \{S\_3\}$ with the total cost 12+5=17.

---

The unweighted version (when the weights of the elements are all 1)
is also very interesting to me.

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness, packing
> **Comments:**
> **username_1**: An easy statement about the complexity is to reduce from Weighted Set Cover by simply setting $k=|S|$.  
> **username_2**: If I understand your question correctly, you're asking for an algorithm to solve the *weighted set cover problem* with bounded size, $k$. If you solve the normal *weighted set cover problem* and find that the minimum cover $C$ requires size $k'$, then don't you simply use $C$ if $k' \leq k$ and declare *no solution* otherwise?  
> **username_0**: 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.  
> **username_3**: My understanding is as follows. You have $S = \{S_1, S_2, ... S_m\}$. A configuration is a subset of $S$ with size $\leq k$. The cost of a configuration $C$ is $\sum_{x \in \bigcup C} w(x)$. You want to find a collection of $\leq |U|$ configurations minimizing $\sum_i cost(C_i)$ subject to $\bigcup \bigcup_i C_i = U$.  If my understanding is correct, then setting $k=1$ and $w(x)=1$ everywhere means that your cost will be exactly $|U|$ iff the system has an exact cover, doesn't it? It shouldn't get any easier for larger $k$, but that takes an argument that won't fit in the 3 characters left.  
> **username_0**: Hi Yonatan. Obviously, any subset should be part of exactly one configuration. Setting $k=1$ and  $w(x)=1$ everywhere means that the cost may be larger than $|U|$. This is because there may be overlaps between the sets in $S$. What you claim is true - the total cost will be equal to $|U|$ iff every element is included in exactly one subset.  
> **username_3**: Oh. That second sentence wasn't clear from the initial post, I think. In that case, my comment is not relevant.  
> **username_0**: No, I think it is. Consider the objective function of such a problem. It is never beneficial to select this subset more than 1 time (in the same or different configurations).  
> **username_0**: Thanks Yonatan for your previous comment. I just updated the description of the problem.  
> **username_4**: Even after the clarifying remarks, I don't understand the statement of the problem.  
> **username_0**: There is one more update in the description!  
> **username_5**: You don't define what is a configuration and it doesn't seem that configurations are given as input. You should edit the question and clarify exactly what is the input for the problem. Then you should clarify what is the output (e.g. is it a partition of S which minimizes the cost of the partition where the cost of a partition is the sum of cost of intersections of members of S in each part?)  
> **username_5**: I edited the question for clarification based on my understanding, please check the edited version and feel free to edit further.  
> **username_5**: [cross posted](http://cs.stackexchange.com/q/55037/) on [cs.se].  

---

## 1 answers

### Answer by username_4 on 2016-04-01. Score: 1

I believe it's NP-hard, by a reduction from [min-balanced cut](https://www.nada.kth.se/~viggo/wwwcompendium/node95.html). Given a graph $G=(V,E)$ and integer $\ell$, min-balanced cut asks whether there is a cut that is balanced (has $|V|/2$ vertices on each side), and cuts at most $\ell$ edges. Given $G$ and $\ell$, construct the following instance of your problem. For each vertex $v$, create a set $S\_v$ containing the edges incident to $v$. Take $k=|V|/2$. Then the (minimal) $k$-good partitions are partitions of the sets into two equal-size groups, corresponding to the balanced cuts of $G$, and your (unweighted) cost for such a solution equals $|E|$ plus the number of edges cut. Unless I'm mistaken :-).

EDIT: Similarly you can reduce the following problem to yours: given a graph $G=(V,E)$ and integer $\ell$, color the vertices of $G$ so that each color class has at most $k$ vertices, minimizing the number of edges whose two endpoints have the same color. (The reduction: make a set $S\_v$ for each vertex $v\in V$, containing the pairs $\{v,w\}$ not in $E$.)


---

