Will a Greedy algorithm give a correct result for minimum partition?

Question

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?

Answer 1

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\}$

Answer 2

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.