Understanding Popular Matchings via Stable Matchings
From MaRDI portal
Publication:5028352
DOI10.1137/19M124770XzbMath1483.91135arXiv1811.06897MaRDI QIDQ5028352
Ágnes Cseh, Telikepalli Kavitha, Yuri Faenza, Vladlena Powers
Publication date: 9 February 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.06897
05C90: Applications of graph theory
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91B68: Matching models
Related Items
Quasi-Popular Matchings, Optimality, and Extended Formulations, Popular critical matchings in the many-to-many setting
Cites Work
- Unnamed Item
- Popular mixed matchings
- Linear programming brings marital bliss
- Characterization of stable matchings as extreme points of a polytope
- A new fixed point approach for stable networks and stable marriages
- Network flow and 2-satisfiability
- Popular edges and dominant matchings
- Popular matchings in the stable marriage problem
- The Geometry of Fractional Stable Matchings and Its Applications
- Popular Matchings
- Popular Matchings in the Marriage and Roommates Problems
- An efficient algorithm for the “stable roommates” problem
- A New Approach to Stable Matching Problems
- Popular Half-Integral Matchings.
- Popularity, Mixed Matchings, and Self-Duality
- Popular Matching in Roommates Setting Is NP-hard
- Quasi-popular Matchings, Optimality, and Extended Formulations
- Popular Matchings and Limits to Tractability
- Popular Matchings with Two-Sided Preferences and One-Sided Ties
- A Size-Popularity Tradeoff in the Stable Marriage Problem
- College Admissions and the Stability of Marriage