Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability
From MaRDI portal
Publication:3449578
DOI10.1007/978-3-662-48433-3_2zbMath1358.91077arXiv1412.0271OpenAlexW2159293216MaRDI QIDQ3449578
Publication date: 4 November 2015
Published in: Algorithmic Game Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.0271
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Matching models (91B68)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- ``Almost stable matchings in the roommates problem with bounded preference lists
- Size versus stability in the marriage problem
- An improved approximation lower bound for finding almost stable maximum matchings
- Efficient algorithms for generalized stable marriage and roommates problems
- Some remarks on the stable matching problem
- A new fixed point approach for stable networks and stable marriages
- Network flow and 2-satisfiability
- On-line algorithms for weighted bipartite matching and stable marriages
- The stable marriage problem with restricted pairs.
- Stable marriage and roommates problems with restricted edges: complexity and approximability
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Deferred acceptance algorithms: history, theory, practice, and open questions
- The Geometry of Fractional Stable Matchings and Its Applications
- The Stable Roommates Problem with Ties
- Total Dual Integrality of Rothblum's Description of the Stable-Marriage Polyhedron
- An efficient algorithm for the “stable roommates” problem
- Approximation Algorithms for Scheduling Problems with Exact Delays
- College Admissions and the Stability of Marriage
This page was built for publication: Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability
