2
$\begingroup$

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

  • 1
    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) ?2010-11-11
  • 0
    @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.2010-11-11
  • 0
    @Pat Is what Djaian is saying correct? If so, can you rewrite your question? In its current form, it's not so clear.2010-11-11

1 Answers 1