The stable marriage problem with master preference lists

DOI10.1016/j.dam.2008.01.002zbMath1175.05111OpenAlexW2028966815MaRDI QIDQ1005239

David F. Manlove, Robert W. Irving, Sandy Scott

Publication date: 9 March 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.01.002

zbMATH Keywords

NP-hardstrongly stablestable matchingweakly stablemaster list including tiesmaster preference liststrictly ordered master listsuper-stable

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

Satisfied two-sided matching: a method considering elation and disappointment of agents ⋮ Stable Matchings with Ties, Master Preference Lists, and Matroid Constraints ⋮ Stable matching of student-groups to dormitories ⋮ The Price of Matching with Metric Preferences ⋮ Stable matchings of teachers to schools ⋮ A Matroid Generalization of the Super-Stable Matching Problem ⋮ Hedonic diversity games: a complexity picture with more than two colors ⋮ Stable marriage with groups of similar agents ⋮ Recognizing when a preference system is close to admitting a master list ⋮ Stable matching with multilayer approval preferences: approvals can be harder than strict preferences ⋮ Recognizing when a preference system is close to admitting a master list ⋮ A simple matching domain with indifferences and a master list ⋮ Stable matching with multilayer approval preferences: approvals can be harder than strict preferences ⋮ Popular matchings with variable item copies ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ Maximum locally stable matchings ⋮ Geometric stable roommates ⋮ Maximum stable matching with one-sided ties of bounded length ⋮ Almost mutually best in matching markets: rank gaps and size of the core ⋮ The hospitals/residents problem with lower quotas

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Student-project allocation with preferences over projects
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Some remarks on the stable matching problem
• Stable marriage and indifference
• Network flow and 2-satisfiability
• Approximability results for stable marriage problems with ties.
• Hard variants of stable marriage.
• A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the Technion
• Minimum Edge Dominating Sets
• The Complexity of Counting Stable Marriages
• Three Fast Algorithms for Four Problems in Stable Marriage
• STACS 2004
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• College Admissions and the Stability of Marriage

This page was built for publication: The stable marriage problem with master preference lists