Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
An Optimal Algorithm for the Popular Condensation Problem
verfasst von : Yen-Wei Wu, Wei-Yin Lin, Hung-Lung Wang, Kun-Mao Chao
Erschienen in: Combinatorial Algorithms
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 an extension of the popular matching problem: the
popular condensation problem
. An instance of the popular matching problem consists of a set of applicants
A
and a set of posts
P
. Each applicant has a strictly ordered preference list, which is a sequence of posts in order of his/her preference. A matching
M
mapping from
A
to
P
is
popular
if there is no other matching
M
′ such that more applicants prefer
M
′ to
M
than prefer
M
to
M
′. Although some efficient algorithms have been proposed for finding a popular matching, a popular matching may not exist for those instances where the competition of some applicants cannot be resolved. The popular condensation problem is to find a popular matching with the minimum number of applicants whose preferences are neglected, that is, to optimally condense the instance to admit a local popular matching. We show that the problem can be solved in
O
(
n
+
m
) time, where
n
is the number of applicants and posts, and
m
is the total length of the preference lists.