Header menu link for other important links
X
Popularity in the generalized hospital residents setting
Published in Springer Verlag
2017
Volume: 10304 LNCS
   
Pages: 245 - 259
Abstract
We consider the problem of computing popular matchings in a bipartite graph G = (R ∪ H, E) where R and H denote a set of res-idents and a set of hospitals respectively. Each hospital h has a positive capacity denoting the number of residents that can be matched to h. The residents and the hospitals specify strict preferences over each other. This is the well-studied Hospital Residents (HR) problem which is a generaliza-tion of the Stable Marriage (SM) problem. The goal is to assign residents to hospitals optimally while respecting the capacities of the hospitals. Sta-bility is a well-accepted notion of optimality in such problems. However, motivated by the need for larger cardinality matchings, alternative notions of optimality like popularity have been investigated in the SM setting. In this paper, we consider a generalized HR setting – namely the Laminar Classified Stable Matchings (LCSM+) problem. Here, additionally, hospi-tals can specify classifications over residents in their preference lists and classes have upper quotas. We show the following new results: We define a notion of popularity and give a structural characterization of popular matchings for the LCSM+ problem. Assume n = |R| + |H| and m = |E|. We give an O(mn) time algorithm for computing a maximum cardinality popular matching in an LCSM+ instance. We give an O(mn2) time algo-rithm for computing a matching that is popular amongst the maximum cardinality matchings in an LCSM+ instance. © Springer International Publishing AG 2017.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
ISSN03029743
Open AccessYes
Concepts (11)
  •  related image
    Computation theory
  •  related image
    Graph theory
  •  related image
    Bipartite graphs
  •  related image
    Cardinalities
  •  related image
    New results
  •  related image
    POPULAR MATCHING
  •  related image
    PREFERENCE LISTS
  •  related image
    STABLE MARRIAGES
  •  related image
    Structural characterization
  •  related image
    Time algorithms
  •  related image
    Hospitals