<p>The problem can be solved via the assignment problem/network flow. Create a bipartite graph with the left side consisting of $N$ vertices $a_1,\ldots,a_N$ corresponding to the sets $A_1,\ldots,A_n$. The right side has $m$ vertices $u_1,\ldots,u_m$ one for each element in $U$. Connect $a_i$ via directed arcs of capacity $1$ to each element vertex that $A_i$ contains. Now add a source vertex $s$ and connect it via an arc of capacity $k_i$ to $a_i$. Connect each $u_j$ to a sink vertex $t$ with an arc capacity of $1$. The problem has a solution if and only if there is an $s$-$f$ flow of value $\sum_i k_i$ in this network. An integral flow would give you a desired solution.</p>

CC BY-SA 3.0
2011-11-08T16:28:35.673Z
2011-11-08T16:28:35.673Z
Chandra Chekuri
<p>I'm a working software engineer and I'm trying to develop some planning software. I have faced the following problem.</p>

<p>I have some finite set $ U $ of some distinct elements $ e_i \in U $.</p>

<p>I have some subsets $ A_i \subset U $, where $ i \in \{1, 2, \cdots, N\} $.</p>

<p>I have an array of integers $ &lt;k_1, k_2, \cdots, k_N &gt; $. Each integer $ k_i \leq |A_i| $ and $$ \sum_{i \in \{1, 2, \cdots, N\}} k_i \leq | \cup_{i \in \{1, 2, \cdots, N\}} A_i | $$.</p>

<p>I want to find sets $ B_i $, where $ i \in \{1, 2, \cdots, N\} $, such that $ |B_i| = k_i $ and $$ \forall i \in \{1, 2, \cdots, N\} .  B_i \subset A_i $$ and $$ \forall i, j \in \{1, 2, \cdots, N\} . B_i \cap B_j = \emptyset $$</p>

<p>The choice of actual $ B_i $ doesn't matter at all.</p>

<ol>
<li><p>I'd like to find is it possible at all. It seems to me that it is, since it's obviously possible for not intersecting $ A_i $, and if they intersects we can reduce the problem to not intersecting $ A&#39;_i $</p></li>
<li><p>I'd like to find fast algorithm that will not-deterministically choose any $ B_i $. I'd like to find the complexity of the problem. It seems that there should be some fast algorithm and problem doesn't seem similar to NP-hard problems, but I somehow feel that it can be NP-hard.</p></li>
</ol>

<p>The actual environment is that there are around 50 000 000 elements in $ U $ and N is around 100.</p>

<p>Is it some known problem? Where can I read on the matter? Is there any fast algorithm? What is the best way to perform such partitioning in given environment.</p>

CC BY-SA 3.0
2011-11-08T15:54:09.673Z
If I understand correctly, when each $k_i$ is equal to $1$, then this is equivalent to finding a [system of distinct representatives](http://www.cut-the-knot.org/arithmetic/marriage.shtml) (also known as a [transversal](http://en.wikipedia.org/wiki/Transversal)). I'm not sure what happens when $k_i \neq 1$.
mhum
CC BY-SA 3.0
2011-11-08T15:58:06.150Z
Victor: It is not always possible.  For example, consider the case where N=3, k1=k2=k3=1, A1=A2={1}, A3={2,3}.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-09T13:48:23.007Z
You will at least need to strengthen the constraints on the $k_i$ to sums and unions over arbitrary subsets of $\{1,\dots,N\}$. I think it's a simple induction over $N$ to show that this suffices, don't really have time to work it out now, though.
Klaus Draeger
<cc.complexity-theory><nondeterminism><partition-problem>
Set partitioning algorithm
Victor Nazarov
# Set partitioning algorithm

(Asked by: username_0 on 2011-11-08)

I'm a working software engineer and I'm trying to develop some planning software. I have faced the following problem.

I have some finite set $ U $ of some distinct elements $ e\_i \in U $.

I have some subsets $ A\_i \subset U $, where $ i \in \{1, 2, \cdots, N\} $.

I have an array of integers $  $. Each integer $ k\_i \leq |A\_i| $ and $$ \sum\_{i \in \{1, 2, \cdots, N\}} k\_i \leq | \cup\_{i \in \{1, 2, \cdots, N\}} A\_i | $$.

I want to find sets $ B\_i $, where $ i \in \{1, 2, \cdots, N\} $, such that $ |B\_i| = k\_i $ and $$ \forall i \in \{1, 2, \cdots, N\} . B\_i \subset A\_i $$ and $$ \forall i, j \in \{1, 2, \cdots, N\} . B\_i \cap B\_j = \emptyset $$

The choice of actual $ B\_i $ doesn't matter at all.

1. I'd like to find is it possible at all. It seems to me that it is, since it's obviously possible for not intersecting $ A\_i $, and if they intersects we can reduce the problem to not intersecting $ A'\_i $
2. I'd like to find fast algorithm that will not-deterministically choose any $ B\_i $. I'd like to find the complexity of the problem. It seems that there should be some fast algorithm and problem doesn't seem similar to NP-hard problems, but I somehow feel that it can be NP-hard.

The actual environment is that there are around 50 000 000 elements in $ U $ and N is around 100.

Is it some known problem? Where can I read on the matter? Is there any fast algorithm? What is the best way to perform such partitioning in given environment.

**Tags:** cc.complexity-theory, nondeterminism, partition-problem

> **Comments:**
> **username_1**: If I understand correctly, when each $k_i$ is equal to $1$, then this is equivalent to finding a [system of distinct representatives](http://www.cut-the-knot.org/arithmetic/marriage.shtml) (also known as a [transversal](http://en.wikipedia.org/wiki/Transversal)). I'm not sure what happens when $k_i \neq 1$.  
> **username_2**: Victor: It is not always possible.  For example, consider the case where N=3, k1=k2=k3=1, A1=A2={1}, A3={2,3}.  
> **username_3**: You will at least need to strengthen the constraints on the $k_i$ to sums and unions over arbitrary subsets of $\{1,\dots,N\}$. I think it's a simple induction over $N$ to show that this suffices, don't really have time to work it out now, though.  

---

## 1 answers

### Answer by username_4 on 2011-11-08. Score: 3

The problem can be solved via the assignment problem/network flow. Create a bipartite graph with the left side consisting of $N$ vertices $a\_1,\ldots,a\_N$ corresponding to the sets $A\_1,\ldots,A\_n$. The right side has $m$ vertices $u\_1,\ldots,u\_m$ one for each element in $U$. Connect $a\_i$ via directed arcs of capacity $1$ to each element vertex that $A\_i$ contains. Now add a source vertex $s$ and connect it via an arc of capacity $k\_i$ to $a\_i$. Connect each $u\_j$ to a sink vertex $t$ with an arc capacity of $1$. The problem has a solution if and only if there is an $s$-$f$ flow of value $\sum\_i k\_i$ in this network. An integral flow would give you a desired solution.


---

