N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm

Question

So say I have n numbers, where n is even. I want to pair the numbers such that the maximum sum of the pairs is minimized. For example -2, 3, 4, 5. The ideal pairing is (-2, 5), (3, 4), since its maximum sum is 3 + 4 = 7, and that is the minimal sum possible for a max sum in any pairing. The key to the algorithm is to sort the values from least to greatest. Then pair the least with the greatest, and so on, until you reach the center of the ordering.

Example: 3, -2, 4, 5

Algorithm sorts the values: -2 , 3, 4, 5

Then pairs first with last: (-2, 5)

Then pairs the next available first and last: (3, 4)

Terminates since no pairs left.

This is a greedy algorithm and I am trying to prove that it is always correct using a "greedy stays ahead" approach. My issue is that I am struggling to show that the algorithm's maximum sum is always $\leq$ optimal maximum sum. My intention was to suppose for contradiction that the optimal maximum sum is $<$ the algorithm's maximum sum. But I'm not sure how to find a contradiction. How would this proof go?

Answer 1

Can you see why $\max((-2)+5, 3+4) \lt \max(-2+3, 4+5)$?

The reason is simple. Because on the right hand side, the maximum number 5 is not paired with the minimum number.

---

Let the numbers are $a_1\le a_2\le \cdots\le a_n$. Let the numbers be paired in some way.

• If $a_n$ is paired with $a_1$, we are done at this round.

• Suppose $a_n$ is paired with $a_j$, $j\not= 1$. Then $a_1$ is paired with $a_k$ for some $k\not= n$. So we have two pairs, $\{a_n, a_j\}$ and $\{a_1, a_k\}$. The sums of these two pairs are $a_n + a_j$ and $a_1 + a_k$, the large one of which is $a_n+a_j$.

  Let us switch $a_j$ and $a_1$ so that $a_n$ will pair with $a_1$, and $a_j$ will pair with $a_k$. The sums of the two new pairs are $a_n + a_1$ and $a_j + a_k$, both of which is at most $a_n+a_j$, i.e., the large one of them is at most $a_n+a_j$. So after the switch, the maximum sum of the pairs involving $a_n, a_j, a_k, a_1$ does not increase. Since other pairs stays the same, So after the switch, the maximum sum of all pairs does not increase.

Continuing this process, we will make sure the largest number remaining be paired with the smallest number remaining at each round. The maximum sum of the pairs will never increase at each round. After $n/2$ rounds, we will reach the pairing where $a_k$ is paired with $a_{n+1-k}$.

You can see the above approach is indeed the "greedy stays ahead" approach.