2
$\begingroup$

Given are tuples $(a_{11},\dots,a_{1k}), (a_{21},\dots,a_{2k}), \dots, (a_{n1},\dots,a_{nk})$. We want to know if there is a partition of the tuples into two parts, so that for every coordinate $i=1,\dots,k$, the sum of each part is equal to the sum of the other part.

Has this problem been studied before? If $k=1$, it is of course the famous Partition problem. But I cannot find this generalization under the section "Variants and generalizations" in the Wikipedia page.

$\endgroup$
2
$\begingroup$

This is essentially the same problem as partition. Let $M$ be a large enough integer, and replace each tuple $(a_{i1},\ldots,a_{ik})$ with the single integer $\sum_j a_{ij} M^j$. You now have an equivalent instance of PARTITION.

Your problem appears in the literature, under the name multidimensional two-way number partitioning, in Jelena Kojić, Integer linear programming model for multidimensional two-way number partitioning problem.

$\endgroup$

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.