Hungarian algorithm matching one set to itself

Question

I'm looking for a variation on the Hungarian algorithm (I think) that will pair N people to themselves, excluding self-pairs and reverse-pairs, where N is even.

E.g. given N₀ - N₆ and a matrix C of costs for each pair, how can I obtain the set of 3 lowest-cost pairs?

C = [ [ - 5 6 1 9 4 ]
      [ 5 - 4 8 6 2 ]
      [ 6 4 - 3 7 6 ]
      [ 1 8 3 - 8 9 ]
      [ 9 6 7 8 - 5 ]
      [ 4 2 6 9 5 - ] ]

In this example, the resulting pairs would be:

N₀, N₃
N₁, N₄
N₂, N₅

Having typed this out I'm now wondering if I can just increase the cost values in the "bottom half" of the matrix... or even better, remove them.

Is there a variation of Hungarian that works on a non-square matrix?

Or, is there another algorithm that solves this variation of the problem?

Answer 1

Increasing the values of the bottom half can result in an incorrect solution. You can see this as the corner coordinates (in your example coordinates 0,1 and 5,6) of the upper half will always be considered to be in the minimum X pairs, where X is the size of the matrix.

My Solution for finding the minimum X pairs

Take the standard Hungarian algorithm

You can set the diagonal to a value greater than the sum of the elements in the unaltered matrix — this step may allow you to speed up your implementation, depending on how your implementation handles nulls.

1) The first step of the standard algorithm is to go through each row, and then each column, reducing each row and column individually such that the minimum of each row and column is zero. This is unchanged.

The general principle of this solution, is to mirror every subsequent step of the original algorithm around the diagonal.

2) The next step of the algorithm is to select rows and columns so that every zero is included within the selection, using the minimum number of rows and columns. My alteration to the algorithm means that when selecting a row/column, also select the column/row mirrored around that diagonal, but count it as one row or column selection for all purposes, including counting the diagonal (which will be the intersection of these mirrored row/column selection pairs) as only being selected once.

3) The next step is to check if you have the right solution — which in the standard algorithm means checking if the number of rows and columns selected is equal to the size of the matrix — in your example if six rows and columns have been selected. For this variation however, when calculating when to end the algorithm treat each row/column mirrored pair of selections as a single row or column selection. If you have the right solution then end the algorithm here.

4) If the number of rows and columns is less than the size of the matrix, then find the smallest unselected element, and call it k. Subtract k from all uncovered elements, and add it to all elements that are covered twice (again, counting the mirrored row/column selection as a single selection).
My alteration of the algorithm means that when altering values, you will alter their mirrored values identically (this should happen naturally as a result of the mirrored selection process).

Then go back to step 2 and repeat steps 2-4 until step 3 indicates the algorithm is finished.

This will result in pairs of mirrored answers (which are the coordinates — to get the value of these coordinates refer back to the original matrix) — you can safely delete half of each pair arbitrarily.

To alter this algorithm to find the minimum R pairs, where R is less than the size of the matrix, reduce the stopping point in step 3 to R. This alteration is essential to answering your question.

Answer 2

As @Niklas B, stated you are solving Weighted perfect matching problem take a look at this

here is part of document describing Primal-dual algorithm for weighted perfect matching

Please read all and let me know if is useful to you