I have twelve items, each having a value, v. I'd like to group them into 6 pairs that are the best distribution of value across the set. I'd like them to be distributed in such a way that I have the least variance between the best pair by the sum of the value in that pair with the worst pair.

I am essentially codifying a problem presented here: http://caribbeanopendata.ideascale.com/a/dtd/Underserved-Community-Internet-Access-Baskets-for-BWA-Licensees/85150-16663

Edit (example):

blocks (value): J, 98; I, 95; L, 89; F, 61; G, 61; A, 50; K, 47; D, 40; H, 33; E, 30; B, 27; C, 15;

results: (J, I) =>, 193; (L, F) =>, 150; (G, A) =>, 111; (K, D) =>, 87; (H, E) =>, 63; (B, C) =>, 42;

I got this by sorting by value and combining the best values into a pair. However, the variance between the best pair and the worst is 151.

My goal is to be able to minimize that variance.

  • 3
    $\begingroup$ Interesting problem! I misinterpreted at first, thinking of variance in the technical sense. In that case, it is intuitively clear that one should pair smallest with bggest, and so on. That this is best can in fact be proved. $\endgroup$ – André Nicolas Mar 17 '12 at 21:42
  • $\begingroup$ Added an example to show what could happen, but what I ultimately want. $\endgroup$ – Irwin Mar 17 '12 at 22:08
  • 1
    $\begingroup$ Why are you not pairing the biggest with the smallest, second biggest with second smallest, and so on? $\endgroup$ – André Nicolas Mar 18 '12 at 0:56

As André Nicolas commented, you should pair the smallest with the largest, the second smallest with the second largest, and so on. In your example, the pairs' sums turn out to be 113, 122, 119, 94, 101, and 97, so the difference between the least and greatest of these sums is $122-94=28$.

To show that this is the best we can do, suppose that we have some other pairing. Then for some four numbers $a\leq b\leq c\leq d$ we must have made the pairs $(a,b)$ and $(c,d)$, or else $(a,c)$ and $(b,d)$. If we just change these to $(a,d)$ and $(b,c)$, we can only be doing ourselves a favor since $a+b \leq a+c \leq X \leq b+d \leq c+d$ for both $X = a+d$ and $X = b+c$. If originally one of the pairs had the lowest sum, that sum will now be a little higher; if originally one of the pairs had the highest sum, now that sum will be a little lower. (Or it might not matter at all.) If we keep making these switches, we will eventually get the first-with-last, second-with-second-last, etc. pairing, the difference between whose greatest and least sums is therefore as small as that for any other pairing.

Note: when you say "variance", it might confuse people into thinking you're talking about this. Difference is better.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.