Jointly stable matchings

DOI10.4230/LIPICS.ISAAC.2017.56zbMATH Open1457.90131MaRDI QIDQ5136277FDOQ5136277

Kazuya Okamoto, Shuichi Miyazaki

Publication date: 25 November 2020

Recommendations

• Jointly stable matchings
• Stable marriage with ties and bounded length preference lists
• The stable marriage problem with restricted pairs.
• The stable marriage problem with master preference lists
• Stable marriage and indifference

zbMATH Keywords

NP-completenessstable marriage problemstable matchinglinear-time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Abstract computational complexity for mathematical programming problems (90C60) Matching models (91B68)

Cites Work

• Some remarks on the stable matching problem
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The Complexity of Counting Stable Marriages
• Title not available (Why is that?)
• College Admissions and the Stability of Marriage
• On the Complexity of Timetable and Multicommodity Flow Problems
• Algorithmics of Matching Under Preferences
• Stable marriage and indifference
• The structure of stable marriage with indifference
• A polynomial-time algorithm for the bistable roommates problem
• The set of super-stable marriages forms a distributive lattice
• Concerning the maximum number of stable matchings in the stable marriage problem
• Bistable versions of the marriages and roommates problems

Cited In (4)

• Stable matchings with couples
• Jointly stable matchings
• Stable matching with multilayer approval preferences: approvals can be harder than strict preferences
• Title not available (Why is that?)

This page was built for publication: Jointly stable matchings

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