Will a greedy method of picking the item that causes the largest difference each time lead to the optimal result in the minimum partition problem?

Let's say I have a set $\{a_1,a_2,a_3,...a_n\}$, now I have to divide it into two subsets so that the difference between the sums of the two subsets is the minimum possible.

Greedy Method:

I have the given set of numbers and an empty set. On each iteration, I select the number from the first set and check which causes the minimum difference and put that into the second set and repeat the process again.

For example: let us say I have to partition $\{1,2,3,4\}$ into two subsets so that their respective sums are minimum.

So using the above method I would do the following steps:

Select the number that causes the min diff so far ie.

$\{2,3,4\}$ and $\{1\}$ diff = $9$

$\{1,3,4\}$ and $\{2\}$ diff = $6$

$\{1,2,4\}$ and $\{3\}$ diff = $4$

$\{1,2,3\}$ and $\{4\}$ diff = $2$

so the minimum is $\{1,2,3\}$ and $\{4\}$

I use the above configuration and repeat the same process, and I land up with the partition $\{2,3\}$ and $\{4,1\}$ which has a difference of $0$ and is the correct answer.

So, assuming the numbers given are all positive integers, will the greedy method work for all inputs or will it fail for some. Is dynamic programming the only way to get the optimal solution?

  • 2
    $\begingroup$ Your greedy method seems to be similar to this algorithm, which is only an approximation method. The Wikipedia page also gives a counter-example for optimality. $\endgroup$ – Discrete lizard Jan 18 '18 at 10:54

This does not always lead to the optimal solution. For example for input $\{1,11,16,19,20,30,36,40,41\}$ it gives $\{1,11,16,19,20,36\}$ and $\{30,40,41\}$ with a difference of 8, while a difference of 0 is possible: $\{1,40,36,30\}$ and $\{41,20,16,11,19\}$


As Jeff Erickson says in his book, "greedy algorithms never work". (Except in the --rare-- cases where they do, and they offer simple, efficient approximations to many NP-hard search problems, see for instance Kun's "When Greedy Algorithms are Good Enough: Submodularity and the (1 – 1/e)-Approximation", check also Krause and Golovin's survey for more in-depth discussion.


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.