The subset sum problem of partitioning a multiset of integers into two multisets with equal sums is NP-complete. Is the seemingly related problem of partitioning a multiset of integers into two multisets with equal averages also known to be NP-complete? Does the problem have a received name? I have found no formal analysis of the problem online, only an occasional speculation that the problem may be “hard.”
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
One NP-hard variant of the PARTITION problem is as follows:
INSTANCE: $2k$ positive integers $a_1,\ldots,a_{2k}$ with $\sum_{i=1}^{2k}a_i=2A$
QUESTION: Does there exist an index set $I\subseteq\{1,\ldots,2k\}$ with $|I|=k$ so that $\sum_{i\in I}a_i=A$?
Take the integers $a_1,\ldots,a_{2k}$ together with two copies of the integer $100kA$. It is straightforward to see that these $2k+2$ numbers allow a partition into two sets with equal averages, if and only if the original instance of PARTITION has answer yes.
-
1$\begingroup$ Thank you! In your reduction of PARTITION to the average equalization problem, the two auxiliary integers must be large enough so that the equalisation of the averages (i) places the two large integers into different subsets, and (ii) the subsets are necessarily of equal sizes. $\endgroup$ Commented Aug 20, 2018 at 22:50