<p>Intuitively, you are looking for partitioning the given numbers into k sets that are all have the same sum. Indeed, otherwise, you can benefit by taking two of these sets, and make them as balanced as possible. </p>

<p>As such, you can take an approximation algorithm for subset sum, and turn it into an approximation algorithm to partition. Then extend it to handle $k$-sides partitions, and you would get the required approximation. See for example here: <a href="http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/08_approx_III.pdf" rel="nofollow">http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/08_approx_III.pdf</a></p>

<p>Then you need to modify it to care about your target function....</p>

<p>I assume that going through the details, you would get an $(1+\epsilon)$-approximation algorithm and its running time would be $(n/\epsilon)^{O(k)}$. But better running time might be possible if you are more careful. </p>

CC BY-SA 3.0
2012-02-03T23:27:35.893Z
2012-02-03T23:27:35.893Z
Sariel Har-Peled
<p>I am looking for some approximate algorithm with upper/lower bound for the following problem:</p>

<ul>
<li>Given a set of positive integers $\{a_1, a_2, \dots, a_n\}$, partition $\{1, 2, \dots, n\}$ into disjoint sets $S_1, S_2, \dots, S_k$ so that the following function is maximized:</li>
</ul>

<p>$$
\prod_{i=1}^{n} \sum_{j \in S_i} a_j
$$</p>

<p>Here is a few things I guess about the above problem (Let's call it PSM),</p>

<ol>
<li><p>PSM is very similar to the <a href="http://en.wikipedia.org/wiki/Multiprocessor_scheduling" rel="nofollow noreferrer">multi-processor scheduling problem</a> (with k processors and $a_i$'s as the job lengths) with a slightly different objective function. This is quite simple to show that PSM is at least as hard as multi-processor scheduling problem. Assume we are given a solution to PSM. The makespan of the solution must be minimum (it means this is a solution to the multi-processor scheduling problem as well), otherwise the product of sums is not maximized (right?).</p></li>
<li><p>We cannot have an FPTAS for PSM since multi-processor scheduling is strongly NP-hard.</p></li>
<li><p>For $k$ even, assume we have a $(1+\alpha)$-approximate algorithm for the multi-processor scheduling problem. The algorithm gives an upper bound of $(1-\alpha^2)^{k/2}$ for the PSM problem. That's because the worst case happens when $k/2$ of the sums are $(1+\alpha)\times OPT_{makespan}$ and the rest of them are equal to $(1-\alpha)\times OPT_{makespan}$. Therefore, we find a $((1+\alpha)(1-\alpha))^{k/2} \times OPT_{PSM}$ solution.</p></li>
</ol>

<p>By the way, this is a wireless network scheduling problem. I have already discussed a variation of the problem <a href="https://cstheory.stackexchange.com/questions/5492/np-hardness-of-a-special-case-of-number-partitioning">here</a>.
Any hint, solution, inapproximability result, reference to a book or a paper is appreciated.</p>

CC BY-SA 3.0
2012-02-02T15:48:52.830Z
The partition which maximizes the product of the sums is not necessarily the same as the partition which minimizes the maximum of the sums.  I pointed out a similar fact in a comment to your previous question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-02T21:37:29.777Z
@TsuyoshiIto: Thanks. (1) But I think a solution to the max product of sums is necessarily a solution to the other problem as well. Isn't it? It comes from the fact that in the max product of sums problem, we need to optimize all of the sums, but in the other problem we only optimize the max sum, but not the rest of the sums. If it is not the only cause of the diference, do you have a counter example in mind?
Helium
CC BY-SA 3.0
2012-02-02T21:39:17.157Z
(2) Even if they have totally different solutions, my analysis above (part 3) is correct, I think.
Helium
CC BY-SA 3.0
2012-02-03T23:55:06.320Z
(1) I would be surprised if that holds. But I do not have a counterexample.  (2) Probably an approximation algorithm for minimizing the max of sums (makespan minimization) indeed implies some approximation algorithm for PSM, but I fail to follow your argument: “the worst case happens when k/2 of the sums are (1+α)×OPT and the rest of them are equal to (1−α)×OPT.”  Why?  I assume that OPT means the optimal for the makespan minimization, but then it seems to me that you are somehow assuming that the average of the sums is equal to OPT (that is, you can make the k sums all equal).
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-04T04:26:15.367Z
@TsuyoshiIto: We know that if $X+Y$ is a constant, the larger $|X-Y|$ is, the smaller $XY$ would become. So, the worst case happens when half of the sums are $(1+\alpha)\times OPT$ and the rest of them are $(1-\alpha)\times OPT$. On the other hand, $(\sum_i S_i)/k$ is an upper bound for the product of sums maximization problem. I just edited the question and added subscripts to the OPTs to clarify their meanings.
Helium
CC BY-SA 3.0
2012-02-04T04:50:58.337Z
I am still unconvinced, but I do not think that continuing this conversation is fruitful.  Anyway I think that Sariel Har-Peled gave a correct answer.
Tsuyoshi Ito
CC BY-SA 4.0
2024-01-26T16:09:52.027Z
A small observation: it seems likely that this problem can also be shown to be strongly NP-hard by reduction from the (strongly NP-hard) 3-partition problem (i.e., can a given set of integers be partitioned into triples, all having the same sum).
Neal Young
<cc.complexity-theory><np-hardness><approximation-algorithms><application-of-theory><polynomial-time>
Approximate bound/algorithm for "product of sums maximization" problem
Helium
# Approximate bound/algorithm for "product of sums maximization" problem

(Asked by: username_0 on 2012-02-01)

I am looking for some approximate algorithm with upper/lower bound for the following problem:

* Given a set of positive integers $\{a\_1, a\_2, \dots, a\_n\}$, partition $\{1, 2, \dots, n\}$ into disjoint sets $S\_1, S\_2, \dots, S\_k$ so that the following function is maximized:

$$
\prod\_{i=1}^{n} \sum\_{j \in S\_i} a\_j
$$

Here is a few things I guess about the above problem (Let's call it PSM),

1. PSM is very similar to the [multi-processor scheduling problem](http://en.wikipedia.org/wiki/Multiprocessor_scheduling) (with k processors and $a\_i$'s as the job lengths) with a slightly different objective function. This is quite simple to show that PSM is at least as hard as multi-processor scheduling problem. Assume we are given a solution to PSM. The makespan of the solution must be minimum (it means this is a solution to the multi-processor scheduling problem as well), otherwise the product of sums is not maximized (right?).
2. We cannot have an FPTAS for PSM since multi-processor scheduling is strongly NP-hard.
3. For $k$ even, assume we have a $(1+\alpha)$-approximate algorithm for the multi-processor scheduling problem. The algorithm gives an upper bound of $(1-\alpha^2)^{k/2}$ for the PSM problem. That's because the worst case happens when $k/2$ of the sums are $(1+\alpha)\times OPT\_{makespan}$ and the rest of them are equal to $(1-\alpha)\times OPT\_{makespan}$. Therefore, we find a $((1+\alpha)(1-\alpha))^{k/2} \times OPT\_{PSM}$ solution.

By the way, this is a wireless network scheduling problem. I have already discussed a variation of the problem [here](https://cstheory.stackexchange.com/questions/5492/np-hardness-of-a-special-case-of-number-partitioning).
Any hint, solution, inapproximability result, reference to a book or a paper is appreciated.

**Tags:** cc.complexity-theory, np-hardness, approximation-algorithms, application-of-theory, polynomial-time
> **Comments:**
> **username_1**: The partition which maximizes the product of the sums is not necessarily the same as the partition which minimizes the maximum of the sums.  I pointed out a similar fact in a comment to your previous question.  
> **username_0**: @TsuyoshiIto: Thanks. (1) But I think a solution to the max product of sums is necessarily a solution to the other problem as well. Isn't it? It comes from the fact that in the max product of sums problem, we need to optimize all of the sums, but in the other problem we only optimize the max sum, but not the rest of the sums. If it is not the only cause of the diference, do you have a counter example in mind?  
> **username_0**: (2) Even if they have totally different solutions, my analysis above (part 3) is correct, I think.  
> **username_1**: (1) I would be surprised if that holds. But I do not have a counterexample.  (2) Probably an approximation algorithm for minimizing the max of sums (makespan minimization) indeed implies some approximation algorithm for PSM, but I fail to follow your argument: “the worst case happens when k/2 of the sums are (1+α)×OPT and the rest of them are equal to (1−α)×OPT.”  Why?  I assume that OPT means the optimal for the makespan minimization, but then it seems to me that you are somehow assuming that the average of the sums is equal to OPT (that is, you can make the k sums all equal).  
> **username_0**: @TsuyoshiIto: We know that if $X+Y$ is a constant, the larger $|X-Y|$ is, the smaller $XY$ would become. So, the worst case happens when half of the sums are $(1+\alpha)\times OPT$ and the rest of them are $(1-\alpha)\times OPT$. On the other hand, $(\sum_i S_i)/k$ is an upper bound for the product of sums maximization problem. I just edited the question and added subscripts to the OPTs to clarify their meanings.  
> **username_1**: I am still unconvinced, but I do not think that continuing this conversation is fruitful.  Anyway I think that Sariel Har-Peled gave a correct answer.  
> **username_2**: A small observation: it seems likely that this problem can also be shown to be strongly NP-hard by reduction from the (strongly NP-hard) 3-partition problem (i.e., can a given set of integers be partitioned into triples, all having the same sum).  

---

## 1 answers

### Answer by username_3 on 2012-02-03. Score: 4

Intuitively, you are looking for partitioning the given numbers into k sets that are all have the same sum. Indeed, otherwise, you can benefit by taking two of these sets, and make them as balanced as possible.

As such, you can take an approximation algorithm for subset sum, and turn it into an approximation algorithm to partition. Then extend it to handle $k$-sides partitions, and you would get the required approximation. See for example here: <http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/08_approx_III.pdf>

Then you need to modify it to care about your target function....

I assume that going through the details, you would get an $(1+\epsilon)$-approximation algorithm and its running time would be $(n/\epsilon)^{O(k)}$. But better running time might be possible if you are more careful.


---

