partition a sequence of 2n real numbers so that...

Question

Hey there,

I'm currently reading The Algorithm Design Manual and I'm stuck on this exercise. Could you help me out please?

---

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 I can't prove it. Thanks for your help,

John

Answer 1

I think I can prove this for a sequence with no duplicated numbers, and it should be a reasonably simple exercise for the reader to extend the proof to non-unique sequences.

Pair x₀, x_2n together, then pair all other numbers according to an optimal solution.

Now consider the pairing of (x₀, x_2n) against any other pair x_y, x_z from the optimal subset. x_2n + either x_y or x_z will be greater than x_y+x_z and also x_2n+x₀, therefore the pairing of x_2n, x₀ was optimal.

The proof now extends by induction to the pairing of X₁, X_2n-1, and further partitions of the subset, eventually producing the OP's pairing.

Answer 2

Given the input array

x₀ x₁ x₂ ... x_2n

use merge sort to sort it in O( n log n) time to produce a sorted list

x_a0 x_a1 ... x_a2n

where the indices a_i indicate the permutation that you have performed on the initial list to obtain the second list.

I claim then that the pairing that produces the minimum maximum sum over all pairings is the following pairing:

(x_ai, x_a2n-i) for i = 0, 1, ..., n. That is, you group the highest valued number with the lowest valued number available.

Proof

Proceed by induction, for the case 2n=2 this is obvious.

Without loss of generality consider that the input is a list of sorted numbers (since if it is not then sort them)

x₀ x₁ x₂ ... x_2n.

Consider the pairing of x_2n with any number, then clearly the minmum sum of this pairing is achieved with (x_2n, x₀).

Now consider the pairing of x_2n-1, either (x_2n,x₀),(x_2n-1,x₁) is the pairings that produce the minumim max sum, or (x_2n,x₁),(x_2n-1,x₀) is, or both are. In the latter case our choice doesn't matter. In the seconds to last case, this is impossible (think about it.) In the general case if we proceed inductively by this process, when we are looking for a pair for x_2n-k, x_k is the lowest unused value that we can pair up with, however; suppose instead we pair up x_k with some other x_2n-j for j < k, to try to get a lower minum sum. This is impossible as, x_2n-j + x_k >= x_2n-k + x_k, so at most we can only achieve the same minimum sum.

This means that choosing (x_2n-k,x_k) gives us the minimum pairings.

Answer 3

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

Proof:

Consider any optimal solution which does not contain (x₀, x_2n). It must contain pairs (x₀, x_a) and (x_b, x_2n) with x₀ ≤ x_a ≤ x_2n and x₀ ≤ x_b ≤ x_2n. Remove those pairs from the solution, and in their place put (x₀, x_2n) and (x_a, x_b). Could the presence of either new pair have "damaged" the solution? The pair (x₀, x_2n) could not have, since its sum is less than or equeal to the sum of (x_b, x_2n) 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), which was a member of the same solution. We have constructed an optimal solution which does contain (x₀, x_2n).

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.