We are given an array and a number K. Partition array into K subsets such that

let MaxSum be the maximum sum of among subsets.

We have to minimize summation =$$\sum_{i=1}^{k}MaxSum-sum(i) $$

Is this problem polynimial time solvable?

  • 3
    $\begingroup$ 1. It's not clear what the summation means. You haven't defined the notation $sum(i)$. Please spend some effort to formulate your question more precisely. 2. Do the subsets have to be contiguous? 3. What's the context where you encountered this problem? Can you credit the original source? $\endgroup$ – D.W. Mar 24 '19 at 14:57
  • 1
    $\begingroup$ 4. We discourage posts that simply state a problem out of context, and expect the community to solve it. What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. Did you try a greedy algorithm? Dynamic programming? See cs.meta.stackexchange.com/q/1284/755. $\endgroup$ – D.W. Mar 24 '19 at 14:57
  • 1
    $\begingroup$ (I notice you've received some of this feedback before in the past: 1, 2.) $\endgroup$ – D.W. Mar 24 '19 at 15:00

I'm assuming by $sum(i)$ you mean that given an ordering of the $k$ partitioned subsets, sum over all elements of the $i$th subset.

The $k=2$ case is the optimization variant of the set partitioning problem (https://en.wikipedia.org/wiki/Partition_problem) which is known to be as hard as subset sum. EDIT: The general case is as difficult by reduction from $k=2$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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