<p>(This is a little more detailed version of my comments on the question.)</p>

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

<p>Note that the input to the <i>k</i>-partition problem is usually defined to be <i>km</i> numbers <em>which may not be all distinct</em>, and this is essential in the standard proof of its NP-completeness (such as the one in <a href="http://en.wikipedia.org/wiki/Computers_and_Intractability%3A_A_Guide_to_the_Theory_of_NP-Completeness" rel="nofollow noreferrer">Garey and Johnson</a>).  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 <i>k</i>-partition problem remains NP-complete even if the numbers in the input are required to be all distinct; see [HWW08] for the case of <i>k</i>=3 (see also <a href="https://cstheory.stackexchange.com/questions/716/computational-complexity-of-the-3-partition-problem-with-distinct-numbers/758#758">Serge Gaspers’s answer</a> to another question), which can be modified easily for larger values of <i>k</i>.</p>

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

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

CC BY-SA 2.5
2011-03-15T20:47:55.670Z
2011-03-15T20:47:55.670Z
2017-04-13T12:32:28.080Z
Tsuyoshi Ito
<p>Consider the following problem,</p>

<ul>
<li>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.</li>
</ul>

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

<ul>
<li>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$. </li>
</ul>

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

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

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

CC BY-SA 2.5
2011-03-15T13:57:38.997Z
(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)
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-15T13:58:03.113Z
(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](http://cstheory.stackexchange.com/questions/716/computational-complexity-of-the-3-partition-problem-with-distinct-numbers) (caution: self-promotion).
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-15T16:24:48.270Z
@Tsuyoshi:If it's now clear that the problem for $k\geqslant 3$ is in NPC then could you post your comment as an answer?
Oleksandr Bondarenko
CC BY-SA 2.5
2011-03-15T17:38:46.547Z
@Oleksandr: I can copy my comments to an answer if turkistany does not mind.  He mentioned the 3-partition problem first.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-15T18:20:22.650Z
@Tsuyoshi, Go ahead, I like your answers.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-03-15T19:30:09.747Z
Thanks guys. Thanks Turkestani, Thanks Tsuyoshi Ito. Sorry for my late response. I'm busy with marking the midterm exams :) That's a simple but wonderful solution. Should I remove my comments and add a little more description to the question?
Helium
CC BY-SA 2.5
2011-03-15T02:46:59.603Z
Hmm.  I'd be interested to see your simple polynomial algorithm for $k=2$.
mjqxxxx
CC BY-SA 2.5
2011-03-15T03:10:46.217Z
Can you please explain why you are interested in this problem and provide some motivation for it?
Kaveh
CC BY-SA 2.5
2011-03-15T03:23:06.000Z
@mjqxxxx: This simple algorithm is here: assume the numbers are sorted, i.e. $a_1 < a_2 < ... < a_n$. Then, for $i \le 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.
Helium
CC BY-SA 2.5
2011-03-15T03:28:54.263Z
@Kaveh: 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.
Helium
CC BY-SA 2.5
2011-03-15T03:40:15.723Z
@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.
Kaveh
CC BY-SA 2.5
2011-03-15T03:50:26.367Z
Are you requiring the partition to be into $m$ equal subsets (each of size $k$)?  This isn't clear from the problem statement.
mjqxxxx
CC BY-SA 2.5
2011-03-15T03:54:07.923Z
@Kaveh: Thanks, I made the changes you told.
Helium
CC BY-SA 2.5
2011-03-15T03:55:16.363Z
@mjqxxxx: Thanks a lot. Yes, the subsets are of a same size. I made the correction to the question.
Helium
CC BY-SA 2.5
2011-03-15T08:34:59.977Z
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).
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-03-15T09:23:53.517Z
Is it obvious that this problem without cardinality constraint is in NPC or P?
Oleksandr Bondarenko
CC BY-SA 2.5
2011-03-15T10:04:31.863Z
Well, in the $m$-way partitioning problem we try to minimize the maximum sum of the numbers in each partition (aka timespan). If I'm not mistaken, the product in my problem is max only if the max sum is minimized (otherwise, reducing the max sum will make the product larger). So it must be NP-hard. By now, I don't care about the completeness.
Helium
<cc.complexity-theory><np-hardness><application-of-theory><polynomial-time>
NP-hardness of a special case of Number Partitioning
Helium
# NP-hardness of a special case of Number Partitioning

(Asked by: username_0 on 2011-03-15)

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\_1m$, 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.

**Tags:** cc.complexity-theory, np-hardness, application-of-theory, polynomial-time
> **Comments:**
> **username_4**: Hmm.  I'd be interested to see your simple polynomial algorithm for $k=2$.  
> **username_5**: Can you please explain why you are interested in this problem and provide some motivation for it?  
> **username_0**: @mjqxxxx: This simple algorithm is here: assume the numbers are sorted, i.e. $a_1 < a_2 < ... < a_n$. Then, for $i \le 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.  
> **username_0**: @Kaveh: 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.  
> **username_5**: @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.  
> **username_4**: Are you requiring the partition to be into $m$ equal subsets (each of size $k$)?  This isn't clear from the problem statement.  
> **username_0**: @Kaveh: Thanks, I made the changes you told.  
> **username_0**: @mjqxxxx: Thanks a lot. Yes, the subsets are of a same size. I made the correction to the question.  
> **username_3**: 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).  
> **username_2**: Is it obvious that this problem without cardinality constraint is in NPC or P?  
> **username_0**: Well, in the $m$-way partitioning problem we try to minimize the maximum sum of the numbers in each partition (aka timespan). If I'm not mistaken, the product in my problem is max only if the max sum is minimized (otherwise, reducing the max sum will make the product larger). So it must be NP-hard. By now, I don't care about the completeness.  
> **username_1**: (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)  
> **username_1**: (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](http://cstheory.stackexchange.com/questions/716/computational-complexity-of-the-3-partition-problem-with-distinct-numbers) (caution: self-promotion).  
> **username_2**: @Tsuyoshi:If it's now clear that the problem for $k\geqslant 3$ is in NPC then could you post your comment as an answer?  
> **username_1**: @Oleksandr: I can copy my comments to an answer if turkistany does not mind.  He mentioned the 3-partition problem first.  
> **username_3**: @Tsuyoshi, Go ahead, I like your answers.  
> **username_0**: Thanks guys. Thanks Turkestani, Thanks Tsuyoshi Ito. Sorry for my late response. I'm busy with marking the midterm exams :) That's a simple but wonderful solution. Should I remove my comments and add a little more description to the question?  

---

## 1 answers

### Answer by username_1 on 2011-03-15. Score: 11 | Accepted answer

(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 (∑*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.

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](http://en.wikipedia.org/wiki/Computers_and_Intractability%3A_A_Guide_to_the_Theory_of_NP-Completeness)). 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](https://cstheory.stackexchange.com/questions/716/computational-complexity-of-the-3-partition-problem-with-distinct-numbers/758#758) 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>


---

