<p>The problem is strongly NP-complete.</p>

<p>Reduction from 3-partition, a strongly NP-complete problem. The multiset <span class="math-container">$S$</span>, <span class="math-container">$|S| = 3m$</span>, <span class="math-container">$\sum_{x \in S} x = n$</span> can be partitioned into tuples of size three of equal sum if and only if <span class="math-container">$A \leq B$</span> where <span class="math-container">$A = S$</span> and <span class="math-container">$B$</span> is <span class="math-container">$m$</span> duplicates of <span class="math-container">$\frac{n}{m}$</span>. If <span class="math-container">$A \leq B$</span>, we can have <span class="math-container">$C = A$</span>. If <span class="math-container">$A \not\leq B$</span>, we must have <span class="math-container">$|C| &gt; |A|$</span>, hence a 3-partition exists if and only if a set <span class="math-container">$C$</span> of size <span class="math-container">$|A|$</span> exists.</p>

<p>As for approximations, a trivial 2-approximation exists, since <span class="math-container">$\max(|A|, |B|) \leq |C| \leq |A| + |B|$</span>. Construction: Build <span class="math-container">$C$</span> by always taking smallest integer in either of <span class="math-container">$A$</span> or <span class="math-container">$B$</span>, then remove it from that set, and subtract it from an arbitrary integer in the other set. The value <span class="math-container">$|C| + |A| + |B|$</span> can only decrease over the course of the algorithm. This also shows that the problem is in NP.</p>

CC BY-SA 4.0
2019-12-30T21:33:17.000Z
A slight technicality, $A\leq B$ can occur using some tuples of length other than 3, so one might want to add the restriction that $a \leq n/2m$ for all $a$ in $A$. (which is still NP-complete)
Zach Hunter
CC BY-SA 4.0
2019-12-29T02:28:59.750Z
2019-12-29T02:28:59.750Z
Antti Röyskö
<p>An integer partition of <span class="math-container">$n$</span>, <span class="math-container">$A$</span>, is a multiset of positive integers such that <span class="math-container">$\sum_{a \in A} a= n$</span>. We say that <span class="math-container">$B \leq A$</span>, if there exists a map <span class="math-container">$\phi: |B| \to |A|$</span>, such that for <span class="math-container">$a \in A$</span>, we have <span class="math-container">$\sum_{b| \phi(b) = a} b = a$</span>.</p>

<p>Given two integer partitions of <span class="math-container">$n$</span>, <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, I was wondering how hard is it to find the smallest <span class="math-container">$C$</span> satisfying both <span class="math-container">$C \leq A$</span>, <span class="math-container">$C \leq B$</span>. (by smallest, I mean minimizing <span class="math-container">$|C|$</span>)</p>

<p>Are any polynomial time algorithms known for this problem?</p>

<p>Considering very simple approximations, I know that <span class="math-container">$|C| \leq n-\min_{X \in \{A,B\}} \sum_{x \in X} \left\lfloor \frac{x}{2}\right\rfloor$</span>. I got this by considering splitting each <span class="math-container">$x$</span> into 2's and 1's. More generally we could say: </p>

<p><span class="math-container">$$ |C| \leq n -\max_{k} \left((k-1)\min_{X\in\{A,B\}} \sum_{x\in X}\left\lfloor\frac{x}{k}\right\rfloor\right)$$</span></p>

<partition-problem><partial-order>
Meet of integer partitions
Zach Hunter
# Meet of integer partitions

(Asked by: username_0 on 2019-12-28)

An integer partition of $n$, $A$, is a multiset of positive integers such that $\sum\_{a \in A} a= n$. We say that $B \leq A$, if there exists a map $\phi: |B| \to |A|$, such that for $a \in A$, we have $\sum\_{b| \phi(b) = a} b = a$.

Given two integer partitions of $n$, $A$, $B$, I was wondering how hard is it to find the smallest $C$ satisfying both $C \leq A$, $C \leq B$. (by smallest, I mean minimizing $|C|$)

Are any polynomial time algorithms known for this problem?

Considering very simple approximations, I know that $|C| \leq n-\min\_{X \in \{A,B\}} \sum\_{x \in X} \left\lfloor \frac{x}{2}\right\rfloor$. I got this by considering splitting each $x$ into 2's and 1's. More generally we could say:

$$ |C| \leq n -\max\_{k} \left((k-1)\min\_{X\in\{A,B\}} \sum\_{x\in X}\left\lfloor\frac{x}{k}\right\rfloor\right)$$

**Tags:** partition-problem, partial-order


---

## 1 answers

### Answer by username_1 on 2019-12-29. Score: 4 | Accepted answer

The problem is strongly NP-complete.

Reduction from 3-partition, a strongly NP-complete problem. The multiset $S$, $|S| = 3m$, $\sum\_{x \in S} x = n$ can be partitioned into tuples of size three of equal sum if and only if $A \leq B$ where $A = S$ and $B$ is $m$ duplicates of $\frac{n}{m}$. If $A \leq B$, we can have $C = A$. If $A \not\leq B$, we must have $|C| > |A|$, hence a 3-partition exists if and only if a set $C$ of size $|A|$ exists.

As for approximations, a trivial 2-approximation exists, since $\max(|A|, |B|) \leq |C| \leq |A| + |B|$. Construction: Build $C$ by always taking smallest integer in either of $A$ or $B$, then remove it from that set, and subtract it from an arbitrary integer in the other set. The value $|C| + |A| + |B|$ can only decrease over the course of the algorithm. This also shows that the problem is in NP.

> **Comments:**
> **username_0**: A slight technicality, $A\leq B$ can occur using some tuples of length other than 3, so one might want to add the restriction that $a \leq n/2m$ for all $a$ in $A$. (which is still NP-complete)  

---

