12

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.

Helium
  • 463
  • 2
  • 12
  • 2
    Hmm. I'd be interested to see your simple polynomial algorithm for $k=2$. – mjqxxxx Mar 15 '11 at 02:46
  • Can you please explain why you are interested in this problem and provide some motivation for it? – Kaveh Mar 15 '11 at 03:10
  • @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 Mar 15 '11 at 03:23
  • @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 Mar 15 '11 at 03:28
  • 2
    @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 Mar 15 '11 at 03:40
  • Are you requiring the partition to be into $m$ equal subsets (each of size $k$)? This isn't clear from the problem statement. – mjqxxxx Mar 15 '11 at 03:50
  • @Kaveh: Thanks, I made the changes you told. – Helium Mar 15 '11 at 03:54
  • @mjqxxxx: Thanks a lot. Yes, the subsets are of a same size. I made the correction to the question. – Helium Mar 15 '11 at 03:55
  • 4
    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 Mar 15 '11 at 08:34
  • Is it obvious that this problem without cardinality constraint is in NPC or P? – Oleksandr Bondarenko Mar 15 '11 at 09:23
  • 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 Mar 15 '11 at 10:04
  • 3
    (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 Mar 15 '11 at 13:57
  • 3
    (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). – Tsuyoshi Ito Mar 15 '11 at 13:58
  • @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 Mar 15 '11 at 16:24
  • @Oleksandr: I can copy my comments to an answer if turkistany does not mind. He mentioned the 3-partition problem first. – Tsuyoshi Ito Mar 15 '11 at 17:38
  • 1
    @Tsuyoshi, Go ahead, I like your answers. – Mohammad Al-Turkistany Mar 15 '11 at 18:20
  • 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 Mar 15 '11 at 19:30

1 Answers1

11

(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

Community
  • 1
Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106