GATE CSE 1990 | Question: 12b

Question

Consider the following problem. Given $n$ positive integers $a_{1}, a_{2}\dots a_n,$ it is required to partition them in to two parts $A$ and $B$ such that, $\displaystyle{}\left|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}\right|$ is minimised

Consider a greedy algorithm for solving this problem. The numbers are ordered so that $a_{1} \geq a_{2} \geq \dots a_{n},$ and at $i^{th}$ step, $a_i$ is placed in that part whose sum in smaller at that step. Give an example with $n=5$ for which the solution produced by the greedy algorithm is not optimal.

Comments

This is the partition problem which is NP-Complete. The greedy algorithm would be selecting the elements in reverse order and in alternating fashion distributing them in a and b. This is an approximation algorithm.

---

any pattern that following the pattern suggested by @Arjun sir is also answer…

12 11 8 8 8

11 10 7 7 7

10 9 6 6 6

9 8 5 5 5

……  and so on. you can also go up and that’s also going to be the answer.

like ,

13 12 9 9 9

or even 13 12 11 11 11 and so on infinite answers are possible…

 

PS : even 20 16 15 9 8 also answer.

Using greedy →  s1={20,9,8}  s2={16,15}  diff= 6

but optimal answer → s1={20,15} s2={16,9,8} diff=2 

Answer 1

Let $S = \{12,11,8,8,8\}$

As per the given greedy algorithm we get $A = \{12,8 \}$ and $B = \{11,8,8\}$ and $|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}| = |20 - 27| = 7.$ 

This is not minimal because if we partition $S$ as $A = \{12,11\}$ and $B = \{8,8,8\}$ we get $|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}| = |23 - 24| = 1.$ 

Thus greedy algorithm fails for this example.

Working algorithm: https://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/ 

Comments

Thankyou, your explanation gave me more understanding.. so basically here we are greedy about maintaining ratio between two parts so we get maximum sum  in both sides and which gives minimum difference.

---

yes. At any time, we have only one number which we can put in A or B ( the number $a_i$ in i ^th step). The greedy algorithm puts this number in the partition which is lagging behind. If it puts the number in partition whose sum is greater, then the difference between the partitions increases even further. You can also say that the algorithm tries to maintain a ratio as close to 1 as possible. It makes locally optimal choices but collectively, they are not optimal globally. The behavior of given greedy algorithm seems right intuitively. But as shown by Arjun sir’s answer, it doesn’t work for all inputs.

---

Sometimes it feels Dynamic Programming is easier than the Greedy approach.

It’s sometimes hard to prove or disprove the correctness of the proposed Greedy approach.

Answer 2

How to build the Greedy Algorithm ?

we have $a_1,a_2,…,a_n$ in set S.

Every element should belongs to either A or B but not both. So, our solution will have $’n’$ steps where in each step, we’ll place one element into either A or B.

Given that, at step i, $a_i$ chosen, 

that means, on step 1, $a_1$ will be placed to either A or B, on step 2, $a_2$ will be placed to either A or B etc

Algorithm like :

put $a_1$ into A

for i=2 to n  

     add $a_i$ in A if Adding it in A makes |(Sum of elements of A + $a_i$) – Sum of elements of B| smaller than |Sum of elements of A – ( Sum of elements of B + $a_i$ )|, else add it in B.

 

1. let S = {18, 10,10,5, 2}, Our greedy algorithm work like :
   step 1 : add $a_1=18$ into A. ==> A={18}, B= ∅ :: sum difference = 18
   step 2 : add $a_2=10$ into B. ==> A={18}, B={10}  :: sum difference = 8
   step 3 : add $a_3=10$ into B. ==> A={18}, B={10,10}  :: sum difference = 2
   step 4 : add $a_4=5$ into B. ==> A={18,5}, B={10,10}  :: sum difference = 3
   step 5 : add $a_5=2$ into B. ==> A={18,5}, B={10,10,2}   :: sum difference = 1

 

2. let S = {30, 10,10,5, 2} Our greedy algorithm work like :
   step 1 : add $a_1=30$ into A. ==> A={30}, B= ∅ :: sum difference = 30
   step 2 : add $a_2=10$ into B. ==> A={30}, B={10}  :: sum difference = 20
   step 3 : add $a_3=10$ into B. ==> A={30}, B={10,10}  :: sum difference = 10
   step 4 : add $a_4=5$ into B. ==> A={30}, B={10,10,5}  :: sum difference = 5
   step 5 : add $a_5=2$ into B. ==> A={30}, B={10,10,5,2}   :: sum difference = 3

 

But if you observe this, first element goes to A then second element should be goes to B

what if i encounter a sequence where $a_1+a_2$ equal to rest of the elements ? then surely our greedy algorithm fails

1. let S = {15, 15,10,10, 10}, Our greedy algorithm work like :
   step 1 : add $a_1=15$ into A. ==> A={15}, B= ∅ :: sum difference = 15
   step 2 : add $a_2=15$ into B. ==> A={15}, B={15}  :: sum difference = 0
   step 3 : add $a_3=10$ into B. ==> A={15,10}, B={15}  :: sum difference = 10
   step 4 : add $a_4=10$ into B. ==> A={15,10}, B={15,10}  :: sum difference = 0
   step 5 : add $a_5=10$ into B. ==> A={15,10,10}, B={15,10}   :: sum difference = 10

But we have A={15,15}, B={10,10,10} which is optimal.