Suppose we had 2 arrays of the same size with positive numbers and we wanted to pair up the elements of each array such that the total difference between the pairs is minimized.

The first thought would be to choose pairs with the minimum difference and so on. But it turns out the correct algorithm is to sort them and them pair accordingly.

Any ideas on how to prove that the latter algorithm correctly minimizes the sum of differences?

  • $\begingroup$ Which idea do you want to prove correct? Note that there is no single correct solution. $\endgroup$ – Raphael Feb 18 '14 at 16:34
  • $\begingroup$ Suppose the optimal solution had two pairs $(a, b)$ and $(A, B)$ with $a < A$ but $B < b$. Can you estimate the sum of differences? What if you swapped the $b$s? $\endgroup$ – Karolis Juodelė Feb 18 '14 at 19:21

Let's follow Karolis's suggestion. Consider any solution with pairs $(a,b)$ and $(A,B)$ with $a \leq A$ and $B \leq b$, and write $A = a + \delta$, $B = b - \epsilon$. If we instead pair them $(a,B),(A,b)$, then instead of $|a-b|+|A-B|$ we get $|a-B|+|A-b|$. So we want to show $$ |a-b|+|A-B| \geq |a-B|+|A-b|. $$ Substitute the expressions for $A,B$: $$ |a-b| + |a-b+\delta+\epsilon| \geq |a-b+\epsilon| + |a-b+\delta|. $$ In terms of $C = a-b$, this is $$ |C| + |C+\delta+\epsilon| \geq |C+\epsilon| + |C+\delta|. $$ Rearranging, this is the same as $$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$ So we need to look at the function $D \mapsto |D+\epsilon| - |D|$, whose values are $$ |D+\epsilon| - |D| = \begin{cases} \epsilon & D \geq 0, \\ 2D+\epsilon & -\epsilon \leq D \leq 0, \\ -\epsilon & D \leq -\epsilon \end{cases} $$ We see that this is an increasing function of $D$, and so $C+\delta \geq C$ implies the inequality we want, $$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy