TY - GEN
T1 - An optimal algorithm for the popular condensation problem
AU - Wu, Yen Wei
AU - Lin, Wei Yin
AU - Wang, Hung Lung
AU - Chao, Kun Mao
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84893143861&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893143861&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-45278-9_35
DO - 10.1007/978-3-642-45278-9_35
M3 - Conference contribution
AN - SCOPUS:84893143861
SN - 9783642452772
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 412
EP - 422
BT - Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers
T2 - 24th International Workshop on Combinatorial Algorithms, IWOCA 2013
Y2 - 10 July 2013 through 12 July 2013
ER -