Hungarian Algorithm with Mutual Pairs?

Question

I'm trying to use the following implementation of the Hungarian Algorithm: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm.

I would like the modify this algorithm so that I can pair a set with itself. That is to say, if "a" is assigned to "b," "b" is also assigned to "a." The only idea I've had is changing the following.

for (int cx = x, cy = y, ty; cx != -2; cx = prv[cx], cy = ty)
    {
            yx[cy] = cx;  
            xy[cx] = cy;  
    }

To the following:

for (int cx = x, cy = y, ty; cx != -2; cx = prv[cx], cy = ty)
    {
            yx[cy] = cx; yx[cx]=cy;
            xy[cx] = cy; xy[cy]=cx;
    }

So that the algorithm always checks paths where the pairings are mutual. However, I'm rather sure this is wrong - the code usually segfaults.

I tried fixing the problem by changing if (max_match == n) to a looser constraint, like if (max_match >= n-1), so that the algorithm is content with a sub-perfect matching. This works sometimes, and when it does, it creates some mutual pairs like I wanted, but some vertices are left unpaired. And there are still segmentation faults.

So, is there any way to fix this problem? Are there other more suitable algorithms for this?

Answer 1

I think what you want is a version of a maximum matching for a graph that is not bipartite. There is an algorithm described for this at http://en.wikipedia.org/wiki/Blossom_algorithm, and the very last paragraph talks about the weighted case. You want a minimum cost matching, but every maximum matching has the same number of edges, so if you negate the cost of each link, or subtract the costs from some very large constant, you turn minimum into maximum.

The general maximum problem is sufficiently constant that I think you will have trouble getting the Hungarian algorithm to do it, because if you could do it with the Hungarian algorithm people wouldn't find the general problem so complicated.

Answer 2

The problem is called optimal non-bipartite matching. A classic reference is: DERIGS, U. (1988). Solving nonbipartite matching problems by shortest path techniques. Annals of Operations Research 13, 225–261. For small sets, simpler methods might be adequate. See: https://gis.stackexchange.com/questions/179559/how-to-group-10k-points-into-closest-pairs There is an R package nbpMatching that addresses the problem.

Incidentally if you try simply to use a bipartite matching algorithm and put a heavy penalty on pairing with yourself, you don't consistently get a pairing. The reason is that a more optimal arrangement can be A paired with B', B paired with C' and C paired with A', or similar such arrangements.

Answer 3

I don't know why you can't just use the same set on both sides of the "normal" Hungarian algorithm and assign "infinity" on the pairing of each element with itself. That will give you a maximum pairing and guarantee that no person is matched with himself.