Consider the following problem,Given a set of $n = k m$ positivenumbers $\{ a_1, \dots, a_n \}$ inwhich $k \ge 3$ is a constant, wewant to partition the set into $m$subsets  of size $k$ so that the product of thesum 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 $im$ assign $a_i$to the subset $i$, for $i>m$, assign itto the subset $ni+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.
NP-hardness of a special case of Number Partitioning
cc.complexity theory;np hardness;application of theory;polynomial time
(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 k3 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 Gasperss 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):594596, Sept. 2008.  http://dx.doi.org/10.1016/j.orl.2008.05.004