# Meet of integer partitions

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

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.
• 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) Dec 30, 2019 at 21:33