Prove optimality of assignment problem

Question

I'm trying to write a proof to prove that given two arrays of numbers both of size $n$, sorting them by increasing order and pairing them by index creates the matching with least cost, where cost of $(a,b)$ is $|a-b|$. In other words, I sort each array independently to get $(a_1,a_2,...,a_n)$ and $(b_1,b_2,...,b_n)$ where $a_i \leq a_j$ and $b_i\leq b_j$ when $i<j$, then pair them by index to get $(a_1,b_1)$, $(a_2,b_2)$,...,$(a_n,b_n)$.

I think a way to do this is to prove that if I take any two pairs $(a_i,b_i)$ and $(a_j,b_j)$ from the sorted arrays and swap them, i.e., resulting in $(a_i,b_j)$ and $(a_j,b_i)$, then:

$$|a_i-b_i|+|a_j-b_j| \leq |a_i-b_j|+|a_j-b_i|$$

But I'm not sure how to do the math to prove this statement. Any help appreciated.

Answer 1

Your answer looks good to me (+1). Here's an alternative presentation that explicitly shows the double-counted intervals in cases 2 and 3.

Case 1 ($a_i \leq a_j \leq b_i \leq b_j$): \begin{align} |a_i-b_i| + |a_j-b_j| &= (b_i-a_i)+(b_j-a_j)\\ &= (b_j-a_i)+(b_i-a_j)\\ &= |a_i-b_j|+|a_j-b_i| \end{align}

Case 2 ($a_i \leq b_i \leq a_j \leq b_j$): \begin{align} |a_i-b_i| + |a_j-b_j| &= (b_i-a_i)+(b_j-a_j) \\ &\le (b_i-a_i)+(b_j-a_j) + 2(a_j-b_i)\\ &= (b_j-a_i)+(a_j-b_i) \\ &= |a_i-b_j|+|a_j-b_i| \end{align}

Case 3 ($a_i \leq b_i \leq b_j \leq a_j$): \begin{align} |a_i-b_i| + |a_j-b_j| &= (b_i-a_i)+(a_j-b_j) \\ &\le (b_i-a_i)+(a_j-b_j) + 2(b_j-b_i)\\ &= (b_j-a_i)+(a_j-b_i) \\ &= |a_i-b_j|+|a_j-b_i| \end{align}

Answer 2

Based on Rob Pratt's hints, I have written the following solution:

$$|a_i-b_i| + |a_j-b_j| \leq |a_i-b_j|+|a_j-b_i| \;\;\;\;(1)$$

Knowing that $a_i\leq a_j$ and $b_i \leq b_j$, there are $4!/2^{2} = 6$ possible cases for the order of the four numbers. However, we can assume, without loss of generality, that $a_i \leq b_i$ and consider the three remaining cases.

3 Cases: $$1) \;a_i \leq a_j \leq b_i \leq b_j$$ $$2) \;a_i \leq b_i \leq a_j \leq b_j$$ $$3) \;a_i \leq b_i \leq b_j \leq a_j$$

Consider case 1: Due to the ordering, we can rewrite inequality (1) without absolute values as such:

$$-(a_i-b_i)+-(a_j-b_j) \leq -(a_i-b_j)+-(a_j-b_i)$$

$$-a_i+b_i-a_j+b_j \leq -a_i+b_j-a_j+b_i$$

$$0 \leq 0$$

which is true, so case 1 satisfies the inequality.

Consider case 2: Due to the ordering, we can rewrite inequality (1) without absolute values as such:

$$-(a_i-b_i)+-(a_j-b_j) \leq -(a_i-b_j)+(a_j-b_i)$$

$$-a_i+b_i-a_j+b_j \leq -a_i+b_j+a_j-b_i$$

$$b_i-a_j \leq a_j-b_i$$

which is true because $b_i\leq a_j$. So, case 2 satisfies the inequality.

Consider case 3: Due to the ordering, we can rewrite inequality (1) without absolute values as such:

$$-(a_i-b_i)+a_j-b_j \leq -(a_i-b_j)+a_j-b_i$$

$$-a_i+b_i+a_j-b_j \leq -a_i+b_j+a_j-b_i$$

$$b_i-b_j \leq -b_i+b_j$$

$$2b_i \leq 2b_j$$

$$b_i\leq b_j$$

Which is true, so case 3 satisfies the inequality.

Hence, because all possible cases satisfy the inequality, the inequality holds.