1 Search Results for "Rawat, Amit"


Document
How Good Are Popular Matchings?

Authors: Krishnapriya A M, Meghana Nasre, Prajakta Nimbhorkar, and Amit Rawat

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)


Abstract
In this paper, we consider the Hospital Residents problem (HR) and the Hospital Residents problem with Lower Quotas (HRLQ). In this model with two sided preferences, stability is a well accepted notion of optimality. However, in the presence of lower quotas, a stable and feasible matching need not exist. For the HRLQ problem, our goal therefore is to output a good feasible matching assuming that a feasible matching exists. Computing matchings with minimum number of blocking pairs (Min-BP) and minimum number of blocking residents (Min-BR) are known to be NP-Complete. The only approximation algorithms for these problems work under severe restrictions on the preference lists. We present an algorithm which circumvents this restriction and computes a popular matching in the HRLQ instance. We show that on data-sets generated using various generators, our algorithm performs very well in terms of blocking pairs and blocking residents. Yokoi [Yokoi, 2017] recently studied envy-free matchings for the HRLQ problem. We propose a simple modification to Yokoi's algorithm to output a maximal envy-free matching. We observe that popular matchings outperform envy-free matchings on several parameters of practical importance, like size, number of blocking pairs, number of blocking residents. In the absence of lower quotas, that is, in the Hospital Residents (HR) problem, stable matchings are guaranteed to exist. Even in this case, we show that popularity is a practical alternative to stability. For instance, on synthetic data-sets generated using a particular model, as well as on real world data-sets, a popular matching is on an average 8-10% larger in size, matches more number of residents to their top-choice, and more residents prefer the popular matching as compared to a stable matching. Our comprehensive study reveals the practical appeal of popular matchings for the HR and HRLQ problems. To the best of our knowledge, this is the first study on the empirical evaluation of popular matchings in this setting.

Cite as

Krishnapriya A M, Meghana Nasre, Prajakta Nimbhorkar, and Amit Rawat. How Good Are Popular Matchings?. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{am_et_al:LIPIcs.SEA.2018.9,
  author =	{A M, Krishnapriya and Nasre, Meghana and Nimbhorkar, Prajakta and Rawat, Amit},
  title =	{{How Good Are Popular Matchings?}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.9},
  URN =		{urn:nbn:de:0030-drops-89440},
  doi =		{10.4230/LIPIcs.SEA.2018.9},
  annote =	{Keywords: bipartite graphs, hospital residents, lower-quotas, popular matchings}
}
  • Refine by Author
  • 1 A M, Krishnapriya
  • 1 Nasre, Meghana
  • 1 Nimbhorkar, Prajakta
  • 1 Rawat, Amit

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 bipartite graphs
  • 1 hospital residents
  • 1 lower-quotas
  • 1 popular matchings

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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