3
$\begingroup$

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 (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. Any hint, solution, inapproximability result, reference to a book or a paper is appreciated.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Feb 2, 2012 at 15:48
  • $\begingroup$ @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? $\endgroup$
    – Helium
    Feb 2, 2012 at 21:37
  • $\begingroup$ (2) Even if they have totally different solutions, my analysis above (part 3) is correct, I think. $\endgroup$
    – Helium
    Feb 2, 2012 at 21:39
  • $\begingroup$ (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). $\endgroup$
    – Tsuyoshi Ito
    Feb 3, 2012 at 23:55
  • $\begingroup$ @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. $\endgroup$
    – Helium
    Feb 4, 2012 at 4:26

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

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