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.0271MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
91B68: Matching models
Related Items
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
