5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Which idea do you want to prove correct? Note that there is no single correct solution. $\endgroup$
    – Raphael
    Feb 18, 2014 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$ Feb 18, 2014 at 19:21

1 Answer 1

2
$\begingroup$

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|. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.