



















Given a set $A$ of $n$ people, with each person having a preference list that ranks a subset of $A$ as his/her acceptable partners in order of preference, we consider the Roommates Problem (RP) and the Marriage Problem (MP) of matching people with their partners. In RP there is no further restriction, while in MP only people of opposite genders can be acceptable partners. For a pair of matchings $X$ and $Y$, let $φ(X,Y)$ denote the number of people who prefer a person they get matched by $X$ to a person they get matched by $Y$, and define an unpopularity factor $u(M)$ of a matching $M$ to be the maximum ratio $φ(M',M) / φ(M,M')$ among all other possible matchings $M'$. In this paper, we develop an algorithm to compute the unpopularity factor of a given matching in $O(m\sqrt{n}\log^2 n)$ time for RP and in $O(m\sqrt{n}\log n)$ time for MP, where $m$ is the total length of people's preference lists. We also generalize the notion of unpopularity factor to a weighted setting where people are given different voting weights and show that our algorithm can be slightly modified to support that setting with the same running time.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。