License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.25
URN: urn:nbn:de:0030-drops-155360
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15536/
Go to the corresponding LIPIcs Volume Portal

Kavitha, Telikepalli

Matchings, Critical Nodes, and Popular Solutions

pdf-format:
LIPIcs-FSTTCS-2021-25.pdf (0.7 MB)

Abstract

We consider a matching problem in a marriage instance G. Every node has a strict preference order ranking its neighbors. There is a set C of prioritized or critical nodes and we are interested in only those matchings that match as many critical nodes as possible. Such matchings are useful in several applications and we call them critical matchings. A stable matching need not be critical. We consider a well-studied relaxation of stability called popularity. Our goal is to find a popular critical matching, i.e., a weak Condorcet winner within the set of critical matchings where nodes are voters. We show that popular critical matchings always exist in G and min-size/max-size such matchings can be efficiently computed.

BibTeX - Entry

@InProceedings{kavitha:LIPIcs.FSTTCS.2021.25,
  author =	{Kavitha, Telikepalli},
  title =	{{Matchings, Critical Nodes, and Popular Solutions}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15536},
  URN =		{urn:nbn:de:0030-drops-155360},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.25},
  annote =	{Keywords: Bipartite graphs, Stable matchings, LP-duality}
}

Keywords: Bipartite graphs, Stable matchings, LP-duality
Collection: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Issue Date: 2021
Date of publication: 29.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI