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 -