CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Fair matchings and related problems

Chien-Chung Huang (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; T. Kavitha ; K. Mehlhorn ; D. Michail
Leibniz International Proceedings in Informatics, LIPIcs: 33rd International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013; Guwahati; India; 12 December 2013 through 14 December 2013 (1868-8969). Vol. 24 (2013), p. 339-350.
[Konferensbidrag, refereegranskat]

© Chien-Chung Huang, Telikepalli Kavitha, Kurt Mehlhorn, and Dimitrios Michail. Let G = (A [ 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.

Nyckelord: Bipartite Vertex Cover , Complementary Slackness , Fairness and Rank-Maximality , Linear Programming Duality , Matching with Preferences



Denna post skapades 2014-10-23.
CPL Pubid: 204721

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)