12
$\begingroup$

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.

Improve this question
$\endgroup$
17
  • 2
    $\begingroup$ Hmm. I'd be interested to see your simple polynomial algorithm for $k=2$. $\endgroup$
    – mjqxxxx
    Commented Mar 15, 2011 at 2:46
  • 2
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Commented Mar 15, 2011 at 3:40
  • 4
    $\begingroup$ 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). $\endgroup$
    – Mohammad Al-Turkistany
    Commented Mar 15, 2011 at 8:34
  • 3
    $\begingroup$ (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) $\endgroup$
    – Tsuyoshi Ito
    Commented Mar 15, 2011 at 13:57
  • 3
    $\begingroup$ (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). $\endgroup$
    – Tsuyoshi Ito
    Commented Mar 15, 2011 at 13:58

1 Answer 1

Reset to default
11
$\begingroup$

(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

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.