An optimal algorithm for the popular condensation problem

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationCombinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers
Pages412-422
Number of pages11
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event24th International Workshop on Combinatorial Algorithms, IWOCA 2013 - Rouen, France
Duration: 2013 Jul 102013 Jul 12

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8288 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Workshop on Combinatorial Algorithms, IWOCA 2013
Country/TerritoryFrance
CityRouen
Period2013/07/102013/07/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'An optimal algorithm for the popular condensation problem'. Together they form a unique fingerprint.

Cite this