<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>9317</REFNUM><AUTHORS><AUTHOR>Sng,C.T.S.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>2010</YEAR><TITLE>Popular Matchings in the Weighted Capacitated House Allocation Problem</TITLE><PLACE_PUBLISHED>Journal of Discrete Algorithms, volume 8</PLACE_PUBLISHED><PUBLISHER>Elsevier Science</PUBLISHER><PAGES>102-116</PAGES><LABEL>Sng:2010:9317</LABEL><KEYWORDS><KEYWORD>Popular matching problem; Priorities; Strict preference lists; Maximum popular matching; Polynomial-time algorithm</KEYWORD></KEYWORDS<ABSTRACT>We consider the problem of finding a popular matching in the
Weighted Capacitated House Allocation problem (WCHA). An
instance of WCHA involves a set of agents and a set of
houses. Each agent has a positive weight indicating his
priority, and a preference list in which a subset of houses
are ranked in strict order. Each house has a capacity that
indicates the maximum number of agents who could be matched
to it. A matching M of agents to houses is popular if there
is no other matching M' such that the total weight of the
agents who prefer their allocation in M' to that in M
exceeds the total weight of the agents who prefer their
allocation in M to that in M'. Here, we give an
O(\sqrt{C}n1+m) algorithm to determine if an instance of
WCHA admits a popular matching, and if so, to find a largest
such matching, where C is the total capacity of the houses,
n1 is the number of agents, and m is the total length of the
agents' preference lists.</ABSTRACT><URL>http://dx.doi.org/10.1016/j.jda.2008.11.008</URL></RECORD></RECORDS></XML>