TY - CHAP

T1 - The Generalized Popular Condensation Problem

AU - Wu, Yen Wei

AU - Lin, Wei Yin

AU - Wang, Hung Lung

AU - Chao, Kun Mao

N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - In this paper, we are concerned with the generalized popular condensation problem, which is an extension of the popular matching problem. An instance of the popular matching problem consists of a set of applicants A, a set of posts P, and a set of preference lists. According to the preference lists, the goal is to match each applicant with at most one unique post so that the resulting matching is “popular.” 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 _. However, such a matching does not always exist. To fulfill the popular matching requirements, a possible manipulation is to neglect some applicants. Given that each applicant is appended with a cost for neglecting, the generalized popular condensation problem asks for a subset of applicants, with minimum sum of costs, whose deletion results in an instance admitting a popular matching. We prove that this problem is NP-hard, and it is also NP-hard to approximate to within a certain factor, assuming ties are involved in the preference lists. For the special case where the costs of all applicants are equal, we show that the problem can be solved in O(√ nm) time, where n is the number of applicants and posts, and m is the total length of the preference lists.

AB - In this paper, we are concerned with the generalized popular condensation problem, which is an extension of the popular matching problem. An instance of the popular matching problem consists of a set of applicants A, a set of posts P, and a set of preference lists. According to the preference lists, the goal is to match each applicant with at most one unique post so that the resulting matching is “popular.” 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 _. However, such a matching does not always exist. To fulfill the popular matching requirements, a possible manipulation is to neglect some applicants. Given that each applicant is appended with a cost for neglecting, the generalized popular condensation problem asks for a subset of applicants, with minimum sum of costs, whose deletion results in an instance admitting a popular matching. We prove that this problem is NP-hard, and it is also NP-hard to approximate to within a certain factor, assuming ties are involved in the preference lists. For the special case where the costs of all applicants are equal, we show that the problem can be solved in O(√ nm) 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=84945179984&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945179984&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-13075-0_48

DO - 10.1007/978-3-319-13075-0_48

M3 - Chapter

AN - SCOPUS:84945179984

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 606

EP - 617

BT - Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings

A2 - Ahn, Hee-Kap

A2 - Shin, Chan-Su

PB - Springer Verlag

ER -