2026-08-10T11:23:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8376 2024-03-06T10:41:57Z ddc:004 open_access

Popular Matchings with Multiple Partners Brandl, Florian Kavitha, Telikepalli Bipartite graphs Linear programming duality Gale-Shapley algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florian Brandl and Telikepalli Kavitha 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.19 urn:nbn:de:0030-drops-83765 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.19 eng https://creativecommons.org/licenses/by/3.0/legalcode