# Maximum combined 1st through nth highest combinations of ai + bi

I have two sets (a,b) of data and I am restricted to using the values in the sets once and only once when they are combined.

For example, the 2nd highest value possible from a data set of a{3,2} and b{2,0} is a1+b2=3. There are two possible ways of combining these two data sets: (1) a1+b1 and a2+b2 which results in values of 5 and 2, and (2) a1+b2 and a2+b1 which results in values of 3 and 4. The (2) combination results in the highest (or maximum) 2nd-high value possible of 3.

Ergo, the 3rd highest value possible from a data set of a{3,2,1} and b{4,3,0} is a1+b3=3. There are six possible ways of combining these two data sets: (1) a1+b1 followed by a2+b2 and a3+b3, which results in values of 7, 5 and 1, and (2) a1+b1 followed by a2+b3 and a3+b2, which results in values of 7, 2 and 4, and (3) a1+b2 followed by a2+b1 and a3+b3, which results in values of 6, 6 and 1, and (4) a1+b2 followed by a2+b3 and a3+b1, which results in values of 5, 2 and 5, and (5) a1+b3 followed by a2+b1 and a3+b2, which results in values of 3, 6 and 4, and (6) a1+b3 followed by a2+b2 and a3+b1, which results in values of 3, 5 and 5. The (5) and (6) combinations both result in a maximum 3rd-highest value of 3, from a1+b3.

By brute force and analogy, I have determined the maximum 1st through nth highest combination of ai+bi in two data sets can be determined as follows:

Maximum Formula 1st-high a1+b1 2nd-high min(a1+b2, a2+b1) 3rd-high min(a1+b3, a2+b2, a3+b1) 4th-high min(a1+b4, a2+b3, a3+b2, a4+b1) ... 8th-high min(a1+b8, a2+b7, a3+b6, a4+b5, a5+b4, a6+b3, a7+b2, a8+b1) ... nth-high min(a1+bn, a2+b(n-1), ... , a(n-1)+b2, an+b1)

I have a handle on the formula, what I want to know is (a) where the answer to this question has been published, and (b) what it is formally described by in mathematics.

I am sure this is not the first time this has come up. Is it addressed in a text book or in the literature?

Thanks

-
Interesting question, but the explanation could be more in mathematical terms. We have 2 sets of $n$ elements. How to find a permutation $\sigma_0$ such that $\min_i(a_i + b_{\sigma_0(i)} ) = \max_{\sigma} \min_i (a_i + b_{\sigma(i)} )$ (where the maximum is over all possible permutations) ? – Djaian Nov 11 '10 at 15:23
@Djaian: And if I understand the OP correctly, the conjecture is that if $a_i$ and $b_j$ are both monotonically decreasing, the optimal permutation is just the reversing permutation. – Rahul Nov 11 '10 at 15:34
@Pat Is what Djaian is saying correct? If so, can you rewrite your question? In its current form, it's not so clear. – Yuval Filmus Nov 11 '10 at 22:40

Let $a = 10,9,0$ and $b = 10,8,0$.
First highest is $a_1+b_1 = 20$, second highest is $a_2+b_1 = 19$, third highest is $a_1+b_2 = 18$. Third highest invalidates your formula.
I think you don't have to take just one element in each set, but give a permutation and consider all the sums, take the minimum. For example, if you consider $a_1 + b_1 = 20$, you can choose $a_2 + b_2 (17)$ and $a_3 + b_3$ (0) which would give 0 as a minimum, or $a_2 + b_3 (9)$ and $a_3 + b_2 (8)$ which would give 8. Thus, for the permutation (1)(2)(3) (i.e. identity), the min is 0, and for the permutation (1)(23) the minimum is 8. The question is for which permutation will the minimum be the highest possible. – Djaian Nov 11 '10 at 16:20