The dynamics of rank-maximal and popular matchings

DOI10.1016/J.TCS.2023.114083MaRDI QIDQ6093577zbMATH OpenOpenAlexFDO

Authors Pratik Ghosal, Adam Kunysz, Katarzyna Paluch

Publication date 7 September 2023

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

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

zbMATH Keywords

dynamic matchingpopular matchingEdmonds-Gallai decompositionrank-maximal matching

Mathematics Subject Classification ID

Matching models (91B68)

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.

Recommendations

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

Cites work

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

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)