Sometimes we can claim we have a greedy solution that gives a good solution, but no way to prove it.
Steps
There are 3 main steps to take for an exchange argument — refer to https://www.cs.cornell.edu/courses/cs482/2007su/exchange.pdf
1 Label the algorithm’s solution, and a general solution.
For example, A = {a1, a2, . . ., ak} is the solution to your algorithm, and O = {o1, o2 , …, om} is an arbitrary solution.
2 Assume that the arbitrary solution is not the same as the the greedy algorithm.
Either:
- An element in A is not an element of O
- 2 consecutive elements have different ordering in A and O
3 Exchange
Swap the elements in question in O (either swap one element out and another in for the first case, or swap the order of the elements in the second case)
Example
Given 2 vectors a and b of the same size n, reorder the elements in the vector, so that the sum of all |ai-bi| is minimal and return the minimum
E1 Input: a = (1, 2, 3), b = (3, 2, 1)
E1 Output: 0
E2 Input: a = (5, 9), b = (8, 15 )
E2 Output: 9
A naive greedy approach might be to pick the lowest |ai-bi| every time, however this is wrong if you observe E2, which will pick 9,8 followed by 5,15 -> outputing 11.
However, if we pick the 2 lowest terms every time, then exclude them from selection next, we can come up with the optimum solution.
How do we prove this is true?
Assume that our solution is a*, b*, where a*(i) < a*(i+1) and b*(i) < b*(i+1)
The other solution is a’, b’, where a’ is sorted by a’(i) < a’(i+1).
Assume that b’ is not the same as b*, so there exists a b’(i) and b’(i+1) such that b’(i) > b’(i+1).
Now if we assume this is true and draw this out.
It can be seen that |a(i)-b(i-1)| ≤ |a(i+1)-b(i)|
which means that the alternative solution is worse than or the same as the greedy solution, as if we continue swapping, there will be no difference between the greedy solution and any arbitrary solution.
