#StackBounty: #reductions #partitions Reduction from 3-partition to ABC-partition

Bounty: 50

The ABC-partition problem is a variant of 3-partition in which, instead of a single set $S$ with $3 m$ positive integers, there are three sets $A, B, C$ with $m$ positive integers in each. The goal is to construct $m$ triplets with the same sum, each of which contains exactly one integer from $A, B$ and $C$.

Here is a reduction from ABC-partition to 3-partition. Given the sets $A, B, C$ and the target sum $T$, construct a set $S$ as the union of the following sets:

  • ${1000a+100 | ain A}$
  • ${1000b+10 | b in B}$
  • ${1000c+1 | cin C}$

and the target sum $1000T + 111$. Obviously, every solution of $A,B,C$ is a solution of $S$. Conversely, in every solution of $S$, there must be exactly one element that ends with 100, one that ends with 10, and one that ends with 1; therefore, it corresponds to a solution of $A,B,C$.

Question: what is a reduction from 3-partition to ABC-partition?


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.