Approximate bound/algorithm for "product of sums maximization" problem 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),


PSM is very similar to the multi-processor scheduling problem (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?).
We cannot have an FPTAS for PSM since multi-processor scheduling is strongly NP-hard.
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.
Any hint, solution, inapproximability result, reference to a book or a paper is appreciated.
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.