文章基本信息

标题：Fair Matchings and Related Problems
本地全文：下载
作者：Chien-Chung Huang ; Telikepalli Kavitha ; Kurt Mehlhorn 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：24
页码：339-350
DOI：10.4230/LIPIcs.FSTTCS.2013.339
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Matching with Preferences; Fairness and Rank-Maximality; Bipartite Vertex Cover; Linear Programming Duality; Complementary Slackness