Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Weighted Popular Matchings
verfasst von : Julián Mestre
Erschienen in: Automata, Languages and Programming
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 study the problem of assigning applicants to jobs. Each applicant has a weight and provides a
preference list
, which may contain ties, ranking a subset of the jobs. An applicant
x
may prefer one matching over the other (or be indifferent between them, in case of a tie) based on the jobs
x
gets in the two matchings and
x
’s personal preference. A matching
M
is
popular
if there is no other matching
M
′ such that the weight of the applicants who prefer
M
′ over
M
exceeds the weight of those who prefer
M
over
M
′.
We present two algorithms to find a popular matching, or in case none exists, to establish so. For the case of strict preferences we develop an
O
(
n
+
m
) time algorithm. When ties are allowed a more involved algorithm solves the problem in
$O(\min(k \sqrt{n}, n) m)$
time, where
k
is the number of distinct weights the applicants are given.