In a variant of the Partition Problem given a multiset $S = \{a_1,\dots,a_n\}$ of positive integer with the total sum $\sum_{i=1}^n a_i = m\,T$, we want to find out if exists a partition $S_1,\dots,S_m$ of $S$ in which $\sum_{a_i\in S_j} a_i = T$ for each $j$.

Now my question is the following: given an instance $S$ of Partition, the instance that we construct by replicating the input $k$ times is equivalent to the initial instance?

To explain better from $S$ we construct a multiset $S' = \bigcup_{i=1}^k S$ in which the total sum is obviously $\sum_{a_i \in S'} a_i = k\,m\,T$ and in which we want to find out if exists a partiton $S'_1,\dots,S'_{k\,m}$ of $S'$ in which $\sum_{a_i\in S'_j} a_i = T$ for each $j$.

Is this new instance equivalent to the previous one? The case in which $S$ admits a partition is simple, because also $S'$ will admit a partition, but when $S$ does not admit a partition can we prove that also $S'$ does not admit one? or otherwise find a counterexample?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.