The dynamics of rank-maximal and popular matchings

DOI10.1016/J.TCS.2023.114083zbMATH Open1522.91168arXiv1703.10594OpenAlexW2604647807MaRDI QIDQ6093577FDOQ6093577

Authors: Pratik Ghosal, Adam Kunysz, Katarzyna Paluch 

Publication date: 7 September 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Given a bipartite graph, where the two sets of vertices are applicants and posts and ranks on the edges represent preferences of applicants over posts, a {em rank-maximal} matching is one in which the maximum number of applicants is matched to their rank one posts and subject to this condition, the maximum number of applicants is matched to their rank two posts, and so on. We study the dynamic version of the problem in which a new applicant or post may be added to the graph and we would like to maintain a rank-maximal matching. We show that after the arrival of one vertex, we are always able to update the existing rank-maximal matching in $mathcalO(min(c^{\prime }n,n^2)+m)$ time, where $n$ denotes the number of applicants, $m$ the number of edges and $c^{\prime }$ the maximum rank of an edge in an optimal solution. Additionally, we update the matching using a minimal number of changes (replacements). All cases of a deletion of a vertex/edge and an addition of an edge can be reduced to the problem of handling the addition of a vertex. As a by-product, we also get an analogous $mathcalO(m)$ result for the dynamic version of the (one-sided) popular matching problem. Our results are based on the novel use of the properties of the Edmonds-Gallai decomposition. The presented ideas may find applications in other (dynamic) matching problems.

Full work available at URL: https://arxiv.org/abs/1703.10594

Recommendations

• Dynamic rank-maximal and popular matchings
• Dynamic rank-maximal matchings
• Rank-maximal matchings

zbMATH Keywords

dynamic matchingpopular matchingEdmonds-Gallai decompositionrank-maximal matching

Mathematics Subject Classification ID

Matching models (91B68)

Cites Work

• Fibonacci heaps and their uses in improved network optimization algorithms
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Faster Scaling Algorithms for Network Problems
• Rank-maximal matchings
• Capacitated Rank-Maximal Matchings
• Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems
• Popular Matchings
• The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems
• An efficient algorithm for the “stable roommates” problem
• The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences
• Bounded unpopularity matchings
• Algorithms and Computation
• Assigning papers to referees
• Voting paths
• Dynamic rank-maximal and popular matchings
• Maintaining Near-Popular Matchings

Cited In (6)

• Popular Matchings: Structure and Strategic Issues
• Popularity, Mixed Matchings, and Self-Duality
• Popular Matchings: Structure and Algorithms
• Quasi-popular Matchings, Optimality, and Extended Formulations
• Dynamic rank-maximal matchings
• Dynamic rank-maximal and popular matchings

This page was built for publication: The dynamics of rank-maximal and popular matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6093577)