Understanding Popular Matchings via Stable Matchings

DOI10.1137/19M124770XzbMath1483.91135arXiv1811.06897OpenAlexW4206620227MaRDI 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

zbMATH Keywords

complexitystable matchingpopular matchingdominant matching

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Related Items (2)

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

This page was built for publication: Understanding Popular Matchings via Stable Matchings