<p>Suppose we have a ground set of <span class="math-container">$n$</span> elements and <span class="math-container">$m$</span> sets are defined over them <span class="math-container">$S_i \subseteq [n]$</span>. Think of the following procedure: At each step take two of the sets, take the union, and add the union back to the pool of all sets. Obviously at each step two sets are taken and one is added. Therefore after exactly <span class="math-container">$m-1$</span> operations only one set is left which is the union of all sets <span class="math-container">$\cup_i S_i$</span>. We want to do this procedure to minimize the total cost. Suppose that if we take the union of two sets <span class="math-container">$A, B$</span> the cost will be <span class="math-container">$|A|+|B|$</span>. This is somewhat similar to matrix chain multiplication, but the order is not predefined. </p>

<p>Now this procedure can be thought of as a tree in the following sense: We start with the leaves of the tree which are the original sets and at each step we merge two, create a parent for these two sets, and repeat the process repeatedly until we end up with the root of the tree. The cost of the tree is drfinef as the sum of sizes of all nodes. The problem is to build it such that the total cost is minimum. Here is an illustration of a tree for four sets <span class="math-container">$S_1, S_2, S_3, S_4$</span>: </p>

<p><a href="https://i.sstatic.net/eqTky.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/eqTky.png" alt="enter image description here"></a></p>

<p>The internal nodes are <span class="math-container">$I_3=S_2\cup S_3, I_2 = I_3\cup S_4$</span> and <span class="math-container">$I_1=S_1\cup I_2$</span>. The total cost is <span class="math-container">$|S_1|+|S_2|+|S_3|+|S_4|+|I_1|+|I_2|+|I_3|$</span>. The problem asks for a tree with minimum cost. Clearly the <span class="math-container">$|S_i|$</span>s here are constant and the construction of tree only affects the <span class="math-container">$|I_i|$</span>s. 
Therefore the real question is how to minimize the internal nodes' costs.  </p>

<p><strong>The motivation</strong> for studying this problem is that it can be thought of as compression scheme for an array of sets. Using this tree we will be able to query things like "does item <span class="math-container">$i$</span> belong to <span class="math-container">$S_j$</span>?". The reason it's a compression is because we can store the elements of each node in a rank/select DS and use the rank/select operations by walking from the root down the leaf corresponding to <span class="math-container">$S_j$</span>. There are rank/select data structures that are roughly of memory complexity <span class="math-container">$O(|S_j|)$</span> and hence the cost that we are minimizing. Here are possible approaches to tackle this problem: </p>

<p><strong>1. Greedy</strong> The obvious greedy thing to do is to chose the pair <span class="math-container">$S_v, S_u$</span> such that <span class="math-container">$|S_u \cup S_v|$</span> is minimized. This  can be shown that this is not globally optimal. Can it be proven to be in a certain proximity of the global solution? </p>

<p><strong>2. Reformulating the cost for a balanced tree</strong> If we denote left and right child of an internal node as <span class="math-container">$l(v), r(v)$</span> respectively, one could right:
<span class="math-container">$$|S_v| = |S_{l(v)} \cup S_{r(v)}|= |S_{r(v)}| + |S_{l(v)}| - |S_{l(v)} \cap S_{r(v)}|$$</span> 
We can apply this rule recursively, staring from the root down to the leaves. If <span class="math-container">$h_v$</span> denotes height of a node, i.e. its distance from the root, one can show by induction:
<span class="math-container">$$cost = \sum_{v\in Leaves} h_v|S_v| -\sum_{v\in Inner} h_v|S_{l(v)} \cap S_{r(v)}|$$</span></p>

<p>The problem with this cost function is that for the inner nodes in the middle of tree we don't have direct access to <span class="math-container">$|S_{l(v)} \cap S_{r(v)}|$</span>. One way to is find an upper bound for terms <span class="math-container">$|S_{l(v)} \cap S_{r(v)}|$</span> so that we're upper bounding the cost. One candidate is:
<span class="math-container">$$|S_{r(v)} \cap S_{l(v)})|\le \frac{1}{|L(r(v))|\times |L(l(v))|} \sum_{v\in L(r(v)),u\in L(l(v))} |S_v\cap S_u| $$</span>
in which <span class="math-container">$L(v)$</span> is the leaves of the subtree rooted by <span class="math-container">$v$</span>. This simply means that if you take the average of intersection of the leaves of the two subtrees it's not more than the intersection between the two nodes at the top. </p>

<p>If we enforce that the tree is perfectly balanced (and for simplicity assuming <span class="math-container">$m = 2^H$</span>) search space boils down to the initial permutation of sets <span class="math-container">$\sigma:[m]\rightarrow [m]$</span>. Besides in a balanced tree number of children of a node is a function of its height <span class="math-container">$L(v) = 2^{H-h_v}$</span>. Therefore we have:
<span class="math-container">$$Cost \le \sum_{v\in T} H |S_v| - \sum_{i\neq j\in [m]} \frac{H - \log_2 |\sigma(i)-\sigma(j)|}{(\sigma(i)-\sigma(j))^2}|S_i\cap S_j|$$</span>
In the first term <span class="math-container">$h_v$</span> is replaced by <span class="math-container">$H$</span> because all leafs are at a predetermined height <span class="math-container">$H = \log_2(m)$</span>. So ignoring the constant terms w.r.t <span class="math-container">$\sigma$</span> we can maximize negative term:
<span class="math-container">$$\max_\sigma \sum_{i\neq j\in [m]} \frac{\log_2 |\sigma(i)-\sigma(j)|}{(\sigma(i)-\sigma(j))^2}|S_i\cap S_j| $$</span>
This can again be reformulated as the following problem:
<span class="math-container">$$\max_\sigma \langle M^\sigma, C\rangle $$</span>
in which <span class="math-container">$M,C\in \mathbb{R}^{m\times m}$</span> are defined as <span class="math-container">$C_{i,j} = |S_i\cap S_j|$</span> and <span class="math-container">$M_{i,j} = \frac{\log_2 |i-j|}{(i-j)^2}$</span> and <span class="math-container">$M^\sigma$</span> is simply matrix <span class="math-container">$M$</span> permutated column-wise and row-wise according to <span class="math-container">$\sigma$</span>. Also <span class="math-container">$\langle \cdot, \cdot \rangle$</span> denotes matrix Frobenius product If we have an oracle that solves this problem efficiently, is this a good approximation or not? </p>

CC BY-SA 4.0
2018-10-12T23:43:20.000Z
Interesting problem! Do you already know whether finding an optimal tree is NP-hard?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2018-10-13T12:13:46.633Z
@a3nm I haven't tried to prove that, but it very much looks like an NP-hard problem. I'm fine with constant approximations of the problem as well though.
AmeerJ
CC BY-SA 4.0
2018-10-14T02:39:07.113Z
Ah, so it doesn't reduce to Huffman Coding because the underlying sets might not be disjoint..  Perhaps [this paper](https://web.engr.illinois.edu/~sgupta49/papers/compaction.pdf) shows this problem to be NP hard and considers approximation algorithms?
Neal Young
CC BY-SA 4.0
2018-10-14T10:12:53.247Z
@NealYoung thank you. The method 2 I suggested is actually searching within the balanced trees. Do you think it could give a tighter bound than $O(\log m)$?
AmeerJ
CC BY-SA 4.0
2018-10-14T12:57:01.203Z
Any algorithm that forces the leaves to be at depth $\Omega(\log m)$ cannot give an $o(\log m)$-approximation.  Consider an example with one set of size $n-\sqrt n$ and $\sqrt n$ sets of size $1$ (so $m=\sqrt n+1$).  OPT is $\Theta(n)$, but any tree where all leaves are at depth $\Omega(\log m)$ will have cost at least $\Omega(n\log m)$.  See also Lemma 4.2 in the paper I linked to.
Neal Young
<optimization><tree><binary-trees><set-system>
Optimal set union tree
AmeerJ
# Optimal set union tree

(Asked by: username_0 on 2018-10-11)

Suppose we have a ground set of $n$ elements and $m$ sets are defined over them $S\_i \subseteq [n]$. Think of the following procedure: At each step take two of the sets, take the union, and add the union back to the pool of all sets. Obviously at each step two sets are taken and one is added. Therefore after exactly $m-1$ operations only one set is left which is the union of all sets $\cup\_i S\_i$. We want to do this procedure to minimize the total cost. Suppose that if we take the union of two sets $A, B$ the cost will be $|A|+|B|$. This is somewhat similar to matrix chain multiplication, but the order is not predefined.

Now this procedure can be thought of as a tree in the following sense: We start with the leaves of the tree which are the original sets and at each step we merge two, create a parent for these two sets, and repeat the process repeatedly until we end up with the root of the tree. The cost of the tree is drfinef as the sum of sizes of all nodes. The problem is to build it such that the total cost is minimum. Here is an illustration of a tree for four sets $S\_1, S\_2, S\_3, S\_4$:

[![enter image description here](https://i.sstatic.net/eqTky.png)](https://i.sstatic.net/eqTky.png)

The internal nodes are $I\_3=S\_2\cup S\_3, I\_2 = I\_3\cup S\_4$ and $I\_1=S\_1\cup I\_2$. The total cost is $|S\_1|+|S\_2|+|S\_3|+|S\_4|+|I\_1|+|I\_2|+|I\_3|$. The problem asks for a tree with minimum cost. Clearly the $|S\_i|$s here are constant and the construction of tree only affects the $|I\_i|$s.
Therefore the real question is how to minimize the internal nodes' costs.

**The motivation** for studying this problem is that it can be thought of as compression scheme for an array of sets. Using this tree we will be able to query things like "does item $i$ belong to $S\_j$?". The reason it's a compression is because we can store the elements of each node in a rank/select DS and use the rank/select operations by walking from the root down the leaf corresponding to $S\_j$. There are rank/select data structures that are roughly of memory complexity $O(|S\_j|)$ and hence the cost that we are minimizing. Here are possible approaches to tackle this problem:

**1. Greedy** The obvious greedy thing to do is to chose the pair $S\_v, S\_u$ such that $|S\_u \cup S\_v|$ is minimized. This can be shown that this is not globally optimal. Can it be proven to be in a certain proximity of the global solution?

**2. Reformulating the cost for a balanced tree** If we denote left and right child of an internal node as $l(v), r(v)$ respectively, one could right:
$$|S\_v| = |S\_{l(v)} \cup S\_{r(v)}|= |S\_{r(v)}| + |S\_{l(v)}| - |S\_{l(v)} \cap S\_{r(v)}|$$
We can apply this rule recursively, staring from the root down to the leaves. If $h\_v$ denotes height of a node, i.e. its distance from the root, one can show by induction:
$$cost = \sum\_{v\in Leaves} h\_v|S\_v| -\sum\_{v\in Inner} h\_v|S\_{l(v)} \cap S\_{r(v)}|$$

The problem with this cost function is that for the inner nodes in the middle of tree we don't have direct access to $|S\_{l(v)} \cap S\_{r(v)}|$. One way to is find an upper bound for terms $|S\_{l(v)} \cap S\_{r(v)}|$ so that we're upper bounding the cost. One candidate is:
$$|S\_{r(v)} \cap S\_{l(v)})|\le \frac{1}{|L(r(v))|\times |L(l(v))|} \sum\_{v\in L(r(v)),u\in L(l(v))} |S\_v\cap S\_u| $$
in which $L(v)$ is the leaves of the subtree rooted by $v$. This simply means that if you take the average of intersection of the leaves of the two subtrees it's not more than the intersection between the two nodes at the top.

If we enforce that the tree is perfectly balanced (and for simplicity assuming $m = 2^H$) search space boils down to the initial permutation of sets $\sigma:[m]\rightarrow [m]$. Besides in a balanced tree number of children of a node is a function of its height $L(v) = 2^{H-h\_v}$. Therefore we have:
$$Cost \le \sum\_{v\in T} H |S\_v| - \sum\_{i\neq j\in [m]} \frac{H - \log\_2 |\sigma(i)-\sigma(j)|}{(\sigma(i)-\sigma(j))^2}|S\_i\cap S\_j|$$
In the first term $h\_v$ is replaced by $H$ because all leafs are at a predetermined height $H = \log\_2(m)$. So ignoring the constant terms w.r.t $\sigma$ we can maximize negative term:
$$\max\_\sigma \sum\_{i\neq j\in [m]} \frac{\log\_2 |\sigma(i)-\sigma(j)|}{(\sigma(i)-\sigma(j))^2}|S\_i\cap S\_j| $$
This can again be reformulated as the following problem:
$$\max\_\sigma \langle M^\sigma, C\rangle $$
in which $M,C\in \mathbb{R}^{m\times m}$ are defined as $C\_{i,j} = |S\_i\cap S\_j|$ and $M\_{i,j} = \frac{\log\_2 |i-j|}{(i-j)^2}$ and $M^\sigma$ is simply matrix $M$ permutated column-wise and row-wise according to $\sigma$. Also $\langle \cdot, \cdot \rangle$ denotes matrix Frobenius product If we have an oracle that solves this problem efficiently, is this a good approximation or not?

**Tags:** optimization, tree, binary-trees, set-system

> **Comments:**
> **username_1**: Interesting problem! Do you already know whether finding an optimal tree is NP-hard?  
> **username_0**: @a3nm I haven't tried to prove that, but it very much looks like an NP-hard problem. I'm fine with constant approximations of the problem as well though.  
> **username_2**: Ah, so it doesn't reduce to Huffman Coding because the underlying sets might not be disjoint..  Perhaps [this paper](https://web.engr.illinois.edu/~sgupta49/papers/compaction.pdf) shows this problem to be NP hard and considers approximation algorithms?  
> **username_0**: @NealYoung thank you. The method 2 I suggested is actually searching within the balanced trees. Do you think it could give a tighter bound than $O(\log m)$?  
> **username_2**: Any algorithm that forces the leaves to be at depth $\Omega(\log m)$ cannot give an $o(\log m)$-approximation.  Consider an example with one set of size $n-\sqrt n$ and $\sqrt n$ sets of size $1$ (so $m=\sqrt n+1$).  OPT is $\Theta(n)$, but any tree where all leaves are at depth $\Omega(\log m)$ will have cost at least $\Omega(n\log m)$.  See also Lemma 4.2 in the paper I linked to.  

---

## 0 answers

