2
$\begingroup$

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
    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.2012-03-17
  • 0
    Added an example to show what could happen, but what I ultimately want.2012-03-17
  • 1
    Why are you not pairing the biggest with the smallest, second biggest with second smallest, and so on?2012-03-18

1 Answers 1