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.