1 Search Results for "Ranjan, Keshav"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.30
Popular Matchings in the Hospital-Residents Problem with Two-Sided Lower Quotas

Authors: Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, and Ankita Sarkar

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
We consider the hospital-residents problem where both hospitals and residents can have lower quotas. The input is a bipartite graph G = (ℛ∪ℋ,E), each vertex in ℛ∪ℋ has a strict preference ordering over its neighbors. The sets ℛ and ℋ denote the sets of residents and hospitals respectively. Each hospital has an upper and a lower quota denoting the maximum and minimum number of residents that can be assigned to it. Residents have upper quota equal to one, however, there may be a requirement that some residents must not be left unassigned in the output matching. We call this as the residents' lower quota. We show that whenever the set of matchings satisfying all the lower and upper quotas is non-empty, there always exists a matching that is popular among the matchings in this set. We give a polynomial-time algorithm to compute such a matching.
Cite as

Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, and Ankita Sarkar. Popular Matchings in the Hospital-Residents Problem with Two-Sided Lower Quotas. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{nasre_et_al:LIPIcs.FSTTCS.2021.30,
  author =	{Nasre, Meghana and Nimbhorkar, Prajakta and Ranjan, Keshav and Sarkar, Ankita},
  title =	{{Popular Matchings in the Hospital-Residents Problem with Two-Sided Lower Quotas}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{30:1--30:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.30},
  URN =		{urn:nbn:de:0030-drops-155419},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.30},
  annote =	{Keywords: Matching, Popularity, Lower quota, Preferences}
}
  • Refine by Author
  • 1 Nasre, Meghana
  • 1 Nimbhorkar, Prajakta
  • 1 Ranjan, Keshav
  • 1 Sarkar, Ankita

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms

  • Refine by Keyword
  • 1 Lower quota
  • 1 Matching
  • 1 Popularity
  • 1 Preferences

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact