# NP-hardness of a special case of Number Partitioning

Consider the following problem,

• Given a set of $n = k m$ positive numbers $\{ a_1, \dots, a_n \}$ in which $k \ge 3$ is a constant, we want to partition the set into $m$ subsets of size $k$ so that the product of the sum of each subset is maximized.

The problem is quite similar to the well known $m$-way number partitioning except we have a limit on the number of numbers in each partition. For $k = 2$ the following simple polynomial algorithm can be proposed,

• assume the numbers are sorted, i.e. $a_1<a_2<...<a_n$. Then, for $i≤m$ assign $a_i$ to the subset $i$, for $i>m$, assign it to the subset $n−i+1$.

It's not hard to see why the algorithm works. Just pick two arbitrary bins. Any swap in the numbers will not increase the amount of the product.

But for larger $k$'s, I'm wondered if the problem can be solved in polynomial time or not? I'd be also thankful if somebody can show it's np-hardness.

Note: I encountered the problem while I was working on a scheduling problem in wireless networks. I found a good heuristic algorithm to solve the problem. But after a while I thought the problem might be theoretically interesting.

• Hmm. I'd be interested to see your simple polynomial algorithm for $k=2$. Mar 15, 2011 at 2:46
• @Mohsen, thanks. I would suggest that you include these comments about motivation, background, and what you know about the k=2 case in the question. That would probably make it more interesting for others. Mar 15, 2011 at 3:40
• My intuition is that the product of the sum of each subset is maximized when the sums are equal or the the maximum pairwise difference is minimum. Under this assumption, we get easy reduction from 3-partition which is NP-complete (for k=3). Mar 15, 2011 at 8:34
• (I removed two comments I posted a few hours ago to rewrite them more accurately.) As turkistany suggested, the k-partition problem is reducible to this problem, and therefore this problem is NP-hard for every constant k≥3. The only relevant property is that the maximum of the product of the sums is at least (∑a_i/k)^m if and only if the numbers can be partitioned into m sets each with size k whose sums are all equal. The product is not always maximized by the partition which minimizes the maximum pairwise difference, but that is irrelevant as long as we consider the exact problem. (more) Mar 15, 2011 at 13:57
• (cont’d) If you require the input to be a set instead of a multiset, this reduction still works because the k-partition problem remains NP-complete even with a set, but be careful because the standard proof of the NP-completeness of the 3-partition problem works only when the input is allowed to contain the same integer more than once. See Computational complexity of the 3-partition problem with distinct numbers (caution: self-promotion). Mar 15, 2011 at 13:58