2026-07-20T05:31:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4384 2024-03-06T10:34:59Z ddc:004 open_access

Fair Matchings and Related Problems Huang, Chien-Chung Kavitha, Telikepalli Mehlhorn, Kurt Michail, Dimitrios Matching with Preferences Fairness and Rank-Maximality Bipartite Vertex Cover Linear Programming Duality Complementary Slackness Let G = (A union B, E) be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let r be the worst rank used. A matching M is fair in G if it has maximum cardinality, subject to this, M matches the minimum number of vertices to rank r neighbors, subject to that, M matches the minimum number of vertices to rank (r-1) neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in G. We also show a scaling based algorithm for the fair b-matching problem. Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation---this can be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chien-Chung Huang and Telikepalli Kavitha and Kurt Mehlhorn and Dimitrios Michail 2013 Is Part Of LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2013.339 urn:nbn:de:0030-drops-43841 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.339 eng https://creativecommons.org/licenses/by/3.0/legalcode