Solving hard stable matching problems involving groups of similar agents

DOI10.1016/j.tcs.2020.08.017zbMath1464.68131arXiv1708.04109OpenAlexW3050067303MaRDI QIDQ2205948

Kitty Meeks, Baharak Rastegari

Publication date: 21 October 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.04109

zbMATH Keywords

stable matchingsstable marriage problemNP-hard problemsparameterized complexityfixed-parameter tractable algorithmsstable roommate problem

Mathematics Subject Classification ID

Matching models (91B68) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

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 ⋮ Stable matching with multilayer approval preferences: approvals can be harder than strict preferences ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• The complexity of approximately counting stable roommate assignments
• The complexity of approximately counting stable matchings
• Stable marriage with covering constraints -- a complete computational trichotomy
• Size versus stability in the marriage problem
• An improved approximation lower bound for finding almost stable maximum matchings
• The stable marriage problem with master preference lists
• An application of simultaneous diophantine approximation in combinatorial optimization
• Hard variants of stable marriage.
• Parameterized algorithms for stable matching with ties and incomplete lists
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Parametrized complexity theory.
• The Revealed Preference Theory of Stable and Extremal Stable Matchings
• Integer Programming with a Fixed Number of Variables
• NP-complete stable matching problems
• Minkowski's Convex Body Theorem and Integer Programming
• How hard is it to satisfy (almost) all roommates
• Algorithmics of Matching Under Preferences
• Max flows in O(nm) time, or better
• Parameterized Algorithms
• Approximation and Online Algorithms
• College Admissions and the Stability of Marriage
• Balanced stable marriage: how close is close enough?

This page was built for publication: Solving hard stable matching problems involving groups of similar agents