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?

• Discrete lizard: 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.

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

• Alex Sherman: This answer is correct for the "naive" greedy solution, but you might also consider the same algorithm, but with a sorted input. With the pre-sorted greedy algorithm, the input from this answer actually does produce the optimal result. However, consider the input {4, 5, 6, 7, 8}. 8 and 7 will be put immediately in separate sets, but they need to be in the same set to sum to the remaining 15. The pre-sorted greedy algorithm will end with {8, 5, 4} and {7, 6} with a difference of 4.

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.