Stable marriage and roommates problems with restricted edges: complexity and approximability
From MaRDI portal
Publication:1751156
DOI10.1016/j.disopt.2016.03.002zbMath1390.91243OpenAlexW2509758454MaRDI QIDQ1751156
Publication date: 24 May 2018
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2016.03.002
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
Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability, Constrained stable marriage with free edges or few blocking pairs, The core of housing markets from an agent's perspective: Is it worth sprucing up your home?, Three-dimensional stable matching with hybrid preferences, New and simple algorithms for stable flow problems, Stable matchings with covering constraints: a complete computational trichotomy, Compact linear programs for 2SAT, The stable marriage problem with ties and restricted edges, Hesitant fuzzy linguistic two-sided matching decision making
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- ``Almost stable matchings in the roommates problem with bounded preference lists
- A maximum stable matching for the roommates problem
- 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
- Stable marriage with ties and bounded length preference lists
- Some remarks on the stable matching problem
- Characterization of stable matchings as extreme points of a polytope
- A new fixed point approach for stable networks and stable marriages
- Some simplified NP-complete graph problems
- Network flow and 2-satisfiability
- On-line algorithms for weighted bipartite matching and stable marriages
- The stable marriage problem with restricted pairs.
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Deferred acceptance algorithms: history, theory, practice, and open questions
- A new solution concept for the roommate problem: \(\mathcal{Q}\)-stable matchings
- The Geometry of Fractional Stable Matchings and Its Applications
- Socially Stable Matchings in the Hospitals/Residents Problem
- The Stable Roommates Problem with Ties
- A necessary and sufficient condition for the existence of a complete stable matching
- An efficient algorithm for the “stable roommates” problem
- Approximation and Online Algorithms
- College Admissions and the Stability of Marriage
