Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
