Fair Matchings and Related Problems

Huang, Chien-Chung; Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios

doi:10.4230/LIPIcs.FSTTCS.2013.339

Document

Fair Matchings and Related Problems

Authors Chien-Chung Huang, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail

Part of: Volume: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2013-12-10

PDF

File

PDF

LIPIcs.FSTTCS.2013.339.pdf

Filesize: 0.51 MB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2013.339
URN: urn:nbn:de:0030-drops-43841

Subject Classification

Keywords

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

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

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.

Cite As Get BibTex

Chien-Chung Huang, Telikepalli Kavitha, Kurt Mehlhorn, and Dimitrios Michail. Fair Matchings and Related Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 339-350, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013) https://doi.org/10.4230/LIPIcs.FSTTCS.2013.339

Author Details

Chien-Chung Huang

Telikepalli Kavitha

Kurt Mehlhorn

Dimitrios Michail

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail