Unpopularity Factor in the Marriage and Roommates Problems
share
We develop an algorithm to compute an unpopularity factor of a given matching in the Roommate Problem (RP) and Marriage Problem (MP). The algorithm runs in O(m√(n)^2 n) time for RP and in O(m√(n) n) time for MP.
READ FULL TEXT