An optimal algorithm for the popular condensation problem

Yen Wei Wu, Wei Yin Lin, Hung Lung Wang, Kun Mao Chao

研究成果: 書貢獻/報告類型會議論文篇章

6 引文 斯高帕斯(Scopus)

摘要

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.

原文英語
主出版物標題Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers
頁面412-422
頁數11
DOIs
出版狀態已發佈 - 2013
對外發佈
事件24th International Workshop on Combinatorial Algorithms, IWOCA 2013 - Rouen, 法国
持續時間: 2013 7月 102013 7月 12

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
8288 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

會議

會議24th International Workshop on Combinatorial Algorithms, IWOCA 2013
國家/地區法国
城市Rouen
期間2013/07/102013/07/12

ASJC Scopus subject areas

  • 理論電腦科學
  • 電腦科學(全部)

指紋

深入研究「An optimal algorithm for the popular condensation problem」主題。共同形成了獨特的指紋。

引用此