The stable marriage problem with master preference lists

DOI10.1016/J.DAM.2008.01.002zbMATH Open1175.05111OpenAlexW2028966815MaRDI QIDQ1005239FDOQ1005239

Authors Robert W. Irving, David F. Manlove, 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-hardstable matchingstrongly stableweakly stablemaster list including tiesmaster preference liststrictly ordered master listsuper-stable

Mathematics Subject Classification ID

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

Recommendations

• Hard variants of stable marriage.
• Stable marriage with ties and bounded length preference lists
• Stable marriage and indifference
• scientific article; zbMATH DE number 2086256
• scientific article; zbMATH DE number 1405659

Cites work

• scientific article; zbMATH DE number 1617265 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 1305096 (Why is no real title available?)
• scientific article; zbMATH DE number 1962834 (Why is no real title available?)
• scientific article; zbMATH DE number 2081005 (Why is no real title available?)
• A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the Technion
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Approximability results for stable marriage problems with ties.
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• College Admissions and the Stability of Marriage
• Hard variants of stable marriage.
• Minimum Edge Dominating Sets
• Network flow and 2-satisfiability
• STACS 2004
• Some remarks on the stable matching problem
• Stable marriage and indifference
• Student-project allocation with preferences over projects
• The Complexity of Counting Stable Marriages
• Three Fast Algorithms for Four Problems in Stable Marriage

Cited in

(29)

• Hedonic diversity games: a complexity picture with more than two colors
• Stable matching of student-groups to dormitories
• The price of matching with metric preferences
• Satisfied two-sided matching: a method considering elation and disappointment of agents
• Recognizing when a preference system is close to admitting a master list
• Stable marriage and indifference
• Stable matching with multilayer approval preferences: approvals can be harder than strict preferences
• Popular matchings with variable item copies
• Bribery and control in stable marriage
• scientific article; zbMATH DE number 6672022 (Why is no real title available?)
• Maximum stable matching with one-sided ties of bounded length
• Pairwise Preferences in the Stable Marriage Problem
• Maximum locally stable matchings
• Stable matchings with ties, master preference lists, and matroid constraints
• A matroid generalization of the super-stable matching problem
• Stable matching with multilayer approval preferences: approvals can be harder than strict preferences
• Solving hard stable matching problems involving groups of similar agents
• Stable marriage with groups of similar agents
• Recognizing when a preference system is close to admitting a master list
• Jointly stable matchings
• A simple matching domain with indifferences and a master list
• Almost mutually best in matching markets: rank gaps and size of the core
• Stable matchings of teachers to schools
• The hospitals/residents problem with lower quotas
• Geometric stable roommates
• Bribery and control in stable marriage
• scientific article; zbMATH DE number 1405659 (Why is no real title available?)
• Multidimensional stable roommates with master list
• Compact Preference Representation in Stable Marriage Problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1005239)