Meet of integer partitions

Question

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

Answer 1

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.