Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Popular Matchings in the Capacitated House Allocation Problem
verfasst von : David F. Manlove, Colin T. S. Sng
Erschienen in: Algorithms – ESA 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
′ such that the number of agents who prefer their allocation in
M
′ to that in
M
exceeds the number of agents who prefer their allocation in
M
to that in
M
′. 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.