<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>8631</REFNUM><AUTHORS><AUTHOR>Sng,C.T.S.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>2007</YEAR><TITLE>Popular matchings in the weighted capacitated house allocation problem</TITLE><PLACE_PUBLISHED>Proceedings of ACiD 2007: the 3rd Algorithms and Complexity in Durham workshop, volume 9 of Texts in Algorithmics, College Publications</PLACE_PUBLISHED><PUBLISHER>N/A</PUBLISHER><PAGES>129-140</PAGES><LABEL>Sng:2007:8631</LABEL><ABSTRACT>We consider the problem of finding a popular matching in the <i>Weighted Capacitated House Allocation problem</i> (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 <i>popular</i> 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}n<sub>1</sub>+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, n<sub>1</sub> is the number of agents, and m is the total length of the agents' preference lists.</ABSTRACT></RECORD></RECORDS></XML>