<p>One NP-hard variant of the PARTITION problem is as follows:</p>

<blockquote>
  <p>INSTANCE: $2k$ positive integers $a_1,\ldots,a_{2k}$ with $\sum_{i=1}^{2k}a_i=2A$<br>
  QUESTION: Does there exist an index set $I\subseteq\{1,\ldots,2k\}$ with $|I|=k$ so that $\sum_{i\in I}a_i=A$?</p>
</blockquote>

<p>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.</p>

CC BY-SA 4.0
2018-08-20T22:50:18.080Z
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.
Romans Pancs
CC BY-SA 4.0
2018-08-20T04:44:06.467Z
2018-08-20T04:44:06.467Z
Gamow
<p>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.”</p>

<np-hardness><subset-sum>
Is partitioning a multiset into two multisets with equal averages NP-complete?
Romans Pancs
# Is partitioning a multiset into two multisets with equal averages NP-complete?

(Asked by: username_0 on 2018-08-20)

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.”

**Tags:** np-hardness, subset-sum

---

## 1 answers

### Answer by username_1 on 2018-08-20. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

