<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>8281</REFNUM><AUTHORS><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>Sng,C.T.S.</AUTHOR></AUTHORS><YEAR>2006</YEAR><TITLE>Popular Matchings in the Capacitated House Allocation Problem</TITLE><PLACE_PUBLISHED>Proceedings of ESA 2006: the 14th Annual European Symposium on Algorithms, volume 4168 of Lecture Notes in Computer Science</PLACE_PUBLISHED><PUBLISHER>Springer Verlag</PUBLISHER><PAGES>492-503</PAGES><ISBN>0302-9743</ISBN><LABEL>Manlove:2006:8281</LABEL><ABSTRACT>We consider the problem of finding a popular matching in the Capacitated House Allocation problem (CHA). An instance of CHA involves a set of agents and a set of houses. Each agent has a preference list in which a subset of houses are ranked in strict order, and each house may be matched to a number of agents that must not exceed its capacity. A matching M is popular if there is no other matching M_0 such that the number of agents who prefer their allocation in M_0 to that in M exceeds the number of agents who prefer their allocation in M to that in M_0. Here, we give an O(\sqrt{C}n_1+m) algorithm to determine if an instance of CHA admits a popular matching, and if so, to find a largest such matching, where C is the total capacity of the houses, n_1 is the number of agents and m is the total length of the agents' preference lists. For the case where preference lists may contain ties, we give an O((\sqrt{C} + n_1)m) algorithm for the analogous problem.</ABSTRACT><URL>http://dx.doi.org/10.1007/11841036_45</URL></RECORD></RECORDS></XML>