Equal partitioning with minimum difference in sum - Algorithms and Problem SolvingAlgorithms and Problem Solving

Equal partitioning with minimum difference in sum - Algorithms and Problem SolvingAlgorithms and Problem Solving

Equal partitioning with minimum difference in sum

Posted on September 7, 2015 by জাহিদ

Given an array consisting of N Numbers.
Divide it into two Equal partitions (in size both contains N/2 elements) such that difference between sum of both partitions is minimum. If number of elements are odd difference in partition size can be at most 1.

The problem is a specialization of SubSet Sum problem which decides whether we can find any two partition that has equal sum. This is an NP-Complete problem.

But, the problem in question asking for 2 such equal partition where the equality holds when we satisfy following two conditions:

• Size of the partitions differ by at most 1
• Sum of the elements in the partitions is minimum

Certainly we are asking here for a suboptimal solution to the more generalized NP-complete problem.

For example, for A=[1, 2, 3, 4, 5, 6, 7, 8, 9], we can have such two partitions {[1, 3, 2, 7, 9], [5, 4, 6, 8]} with sum diff = abs(22-23) = 1.

Our goal is to find suboptimal solution with best approximation ratio. Idea is to partition the array in pairs of element that would distribute the sum as uniformly as possible across the partitions. So, each time we would try to take 2 pairs and put one pair in a partition and the other pair in the other partition.

• Sort the array
• If number of elements in less than 4 then create partitions accordingly for each cases when we have 1 element or 2 element or 3 element in the array.
• Otherwise we will take 2 pair each time and put into two partition such that it minimizes the sum diff.
• Pick the pair(largest, smallest) elemets in the the sorted array and put it to the smaller (wr.to sum) partition.
• Then pick the second largest element and find its buddy to put them in the 'other' partition such that sum of second largest and its buddy minimizes the sum difference of the partitions.
• The above approach will give a suboptimal solution. The problem in NP complete so, we can't have an optimal solution but we can improve the approximation ratio as follows.
• If we have suboptimal solution (ie. sum diff != 0) then we try to improve the solution by swapping a large element in the larger partition with a small element in the smaller partition such that the swap actually minimizes the sum diff.

The O(n^2) time and O(n) space implementation of the above approach is as follows –

Read full article from Equal partitioning with minimum difference in sum - Algorithms and Problem SolvingAlgorithms and Problem Solving