3
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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) $\endgroup$ – Zachary Hunter Dec 30 '19 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.