partition a sequence of 2n real numbers so that

Question

I'm currently reading The Algorithm Design Manual and I'm stuck on this exercise.

---

Take a sequence of 2n real numbers as input. Design an O(n log n) algorithm that partitions the numbers into n pairs, with the property that the partition minimizes the maximum sum of a pair. For example, say we are given the numbers (1,3,5,9). The possible partitions are ((1,3),(5,9)), ((1,5),(3,9)), and ((1,9),(3,5)). The pair sums for these partitions are (4,14), (6,12), and (10,8). Thus the third partition has 10 as its maximum sum, which is the minimum over the three partitions.

---

My guess from some examples is that the solution looks like this:

# in pseudo ruby code
a = [1,3,5,9]
pairs = []
while !a.empty?
    pairs << [a.shift, a.pop]  # [a.first, a.last]
end
pairs

But how to prove it?

Answer 1

The algorithm works because when x₀, x₁, ... x_2n-1 is the sorted list, there is always an optimal solution that contains (x₀, x_2n-1).

Proof:

Consider any optimal solution which does not contain (x₀, x_2n-1). It must contain pairs (x₀, x_a) and (x_b, x_2n-1) with x₀ ≤ x_a ≤ x_2n-1 and x₀ ≤ x_b ≤ x_2n-1. Remove those pairs from the solution, and in their place put (x₀, x_2n-1) and (x_a, x_b). Could the presence of either new pair have "damaged" the solution? The pair (x₀, x_2n-1) could not have, since its sum is less than or equal to the sum of (x_b, x_2n-1) which was a member of the original, optimal solution. Neither again could (x_a, x_b) have caused damage, since its sum is less than or equal to the sum of (x_b, x_2n-1), which was a member of the same solution. We have constructed an optimal solution which does contain (x₀, x_2n-1).

Thus the algorithm you give never forecloses the possibility of finding an optimal solution at any step, and when there are only two values left to pair they must be paired together.