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&lt;a_2&lt;...&lt;a_n$. Then, for $i≤m$ assign $a_i$
to the subset $i$, for $i&gt;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.
(This is a little more detailed version of my comments on the question.)

As turkistany suggested in a comment on the question, this problem is NP-hard for every constant k≥3 by a reduction from the k-partition problem.  The reduction does not change instances at all: just note that the maximum of the product of the sums is at least (∑ai/k)m if and only if the numbers can be partitioned into m sets each with size k whose sums are all equal.

Note that the input to the k-partition problem is usually defined to be km numbers which may not be all distinct, and this is essential in the standard proof of its NP-completeness (such as the one in Garey and Johnson).  Therefore, the reduction above only proves the NP-hardness of a slight generalization of the current problem where the input is allowed to be a multiset instead of a set.  However, this gap can be filled because the k-partition problem remains NP-complete even if the numbers in the input are required to be all distinct; see [HWW08] for the case of k=3 (see also Serge Gaspers’s answer to another question), which can be modified easily for larger values of k.

In addition, everything stated here remains NP-complete/NP-hard even when the numbers in the input are given in unary.

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger.  Multigraph realizations of degree sequences: Maximization is easy, minimization is hard.  Operations Research Letters, 36(5):594–596, Sept. 2008.  http://dx.doi.org/10.1016/j.orl.2008.05.004