DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2017.19

Popular Matchings with Multiple Partners

Authors: Florian Brandl and Telikepalli Kavitha

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract

Our input is a bipartite graph G=(A\cup B,E) where each vertex in A\cup B has a preference list strictly ranking its neighbors. The vertices in A and in B are called students and courses, respectively. Each student a seeks to be matched to cap(a)\geq 1 many courses while each course b seeks cap(b)\geq 1 many students to be matched to it. The Gale-Shapley algorithm computes a pairwise-stable matching (one with no blocking edge) in G in linear time. We consider the problem of computing a popular matching in G - a matching M is popular if M cannot lose an election to any matching where vertices cast votes for one matching versus another. Our main contribution is to show that a max-size popular matching in G can be computed by the 2-level Gale-Shapley algorithm in linear time. This is an extension of the classical Gale-Shapley algorithm and we prove its correctness via linear programming.

Cite as

Florian Brandl and Telikepalli Kavitha. Popular Matchings with Multiple Partners. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{brandl_et_al:LIPIcs.FSTTCS.2017.19,
  author =	{Brandl, Florian and Kavitha, Telikepalli},
  title =	{{Popular Matchings with Multiple Partners}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.19},
  URN =		{urn:nbn:de:0030-drops-83765},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.19},
  annote =	{Keywords: Bipartite graphs, Linear programming duality, Gale-Shapley algorithm}
}

Search Results

Documents authored by Brandl, Florian

Popular Matchings with Multiple Partners

Abstract

Cite as

Thanks for your feedback!

Could not send message