Solving hard stable matching problems involving groups of similar agents
From MaRDI portal
Publication:2205948
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
stable matchingsstable marriage problemNP-hard problemsparameterized complexityfixed-parameter tractable algorithmsstable roommate problem
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