"One-Sided Hungarian" or "Hungarian for Roommate Problem"

137 Views Asked by At

The Hungarian algorithm is a solution to a two-sided matching problem. There are similar "one-sided" matching problems, such as the roommates problem. Like the Hungarian, roommates need to be matched to another. The weight of a pairwise match is $w_{ij}$, and your goal is to find the matching that maximize the total weights.

However unlike the Hungarian, the agents are not differentiated into two sides. Any roommate can pair with any other roommate. Each possible pair has a weight, and like the Hungarian, the goal is to find the roommate arrangements with the maximum possible weights.

Is there a known algorithmic solution to "one-sided" matching problems?

1

There are 1 best solutions below

5
On

I'm not entirely sure if I understand your question, and the details matter in this case. To clarify, let $n\in\mathbb Z_{>0}$, further $[2n]=\{1,\dots,2n\}$ and $\mathcal E=\binom{[2n]}{2}=\{e\subseteq[2n]:|e|=2\}$. Let $K_{2n}=([2n],\mathcal E)$ be the complete graph on $2n$ vertices and let $\mathcal M=\{M\in\binom{\mathcal E}{n}:\bigcup_{e\in M}e=[2n]\}$ be the set of perfect matchings in $K_{2n}$, which are $n$ sets of size $2$ that form a partition of $[2n]$. Finally, we add weights, that is, for each $e\in\mathcal E$ we fix some $w_e\in\mathbb R_{\ge 0}$. For a perfect matching $M\in\mathcal M$ let $W(M)=\sum_{e\in M}w_e$ be the weight of $M$.

My understanding is that you want to find an algorithm that outputs a perfect matching $M\in\mathcal M$ such that for all $M'\in\mathcal M$ we have $W(M')\le W(M)$. I hope I got that right.

As long as we consider $K_{2n}$, it doesn't matter if we consider matchings, maximal matchings, maximum matchings or perfect matchings, because the sets of maximal, maximum and perfect matchings coincide, and any maximum weight matching is a perfect matching without loss of generality (i.e. up to edges with trivial weight). If we consider arbitrary graphs, we have to pay more attention.

I also want to stress that finding a stable matching for the roommates problem differs from the problem at hand. For example, a stable matching does not always exist, a maximum weight matching does.

With this being said, there exist algorithms that find solutions to the maximum weight matching problem in $K_{2n}$ with runtime $\mathcal O(n^3)$, by Edmonds (1965), by Gabow (1974), by Lawler (1976), and by Gabow (1990). More general, for graphs with $m$ edges these algorithms perform best in different regimes, Table 3 in this contribution is an excellent overview. However, as pointed out in the general case maximum weight matchings are maximum weight maximal matchings, but may differ from maximum weight perfect matchings (which are maximum weight maximum matchings).