Abstract
In this paper, we give a simple characterization of a set of popular matchings defined by preference lists with ties. By employing our characterization, we propose a polynomial time algorithm for finding a minimum cost popular matching.
Characterizing a Set of Popular Matchings Defined by Preference Lists with Ties
Related papers
Ranked by semantic similarity β how closely each paper's abstract matches this one (100% = near-identical topic).
- Perfect Matchings and Popularity in the Many-to-Many Setting (2024)72% match
- Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting (2023)68% match
- Extending Stable and Popular Matching Algorithms from Bipartite to Arbitrary Instances (2024)62% match
- A new approach to bipartite stable matching optimization (2024)62% match
- Stable Matching with Ties: Approximation Ratios and Learning (2024)60% match
- Condorcet Dimension and Pareto Optimality for Matchings and Beyond (2026)58% match
- A Tie-breaking based Local Search Algorithm for Stable Matching Problems (2024)57% match
- Clique-free t-matchings in degree-bounded graphs (2024)57% match