title: Maximum weighted pairing algorithm for complete graph
body: <h2>The mathematical problem</h2>
  
  <p>Let there be <em>2n</em> persons, and <code>C(i,j)</code> the "cost" of having <em>i</em> and <em>j</em> work together (the function <code>C</code> is quick to compute, in my case it is a given matrix, and is symmetric). The question is to find the arrangement of <em>2n</em> pairs of persons that minimizes the sum of the costs of each pair.</p>
  
  <p>This should be done in polynomial complexity in <em>n</em>, and implemented relatively easily in the Scilab language (input : cost matrix, output : pairings, for instance a <em>n</em>-by-2 matrix of indexes). I am aware that "relatively easily" is subject to interpretation...</p>
  
  <h2>Previous research</h2>
  
  <p>This problem is actually solved by the Blossom algorithm. See for instance <a href="http://pub.ist.ac.at/~vnk/papers/BLOSSOM5.html" rel="nofollow">this paper</a>.</p>
  
  <p>However, this (and its variants) looks like a nightmare to implement. My real problem is for <em>n=20</em>, so although brute force (= trying all possible pairings) is not OK (brute-forcing <em>n=8</em> took an hour on my computer), pretty much anything better than brute force should do the trick; if I can avoid one week of coding at the cost of one hour of computation I'm in.</p>
  
  <p>I was thinking along the lines of using the <a href="http://en.wikipedia.org/wiki/Hungarian_algorithm" rel="nofollow">Hungarian/Munkres algorithm</a> on a <em>2n</em>-by-<em>2n</em> array filling the diagonal with <code>+%inf</code> and other elements by the symmetric cost matrix, then somehow selecting from the resulting permutation a relevant pairing, but I fail to find a reliable way to do this. (Note, the Hungarian algorithm is already coded for a separate section, so you may use it without cost to the "easy to implement" requirement.)</p>
  
  <p><del>I hope that compared to the blossom-algorithm problem, the completeness of the graph allows for some shortcuts...</del> <em>(Edit: see DE's comment below, this is wrong for semi-obvious reasons)</em></p>