Stable marriage and roommates problems with restricted edges: complexity and approximability
type: Item
instance of: scholarly article
title: Stable marriage and roommates problems with restricted edges: complexity and approximability
zbMATH Open document ID: 1390.91243
author: Ágnes Cseh
author: David F. Manlove
published in: Discrete Optimization
publication date: 2018-05-24T00:00:00Z
Mathematics Subject Classification ID: 91B68
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6872082
zbMATH Keywords: stable matching
zbMATH Keywords: restricted edge
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
full work available at URL: j.disopt.2016.03.002
OpenAlex ID: W2509758454
cites work: College Admissions and the Stability of Marriage
cites work: Q4130997
cites work: Some remarks on the stable matching problem
cites work: An efficient algorithm for the “stable roommates” problem
cites work: Q3995616
cites work: Q3999327
cites work: Deferred acceptance algorithms: history, theory, practice, and open questions
cites work: The stable marriage problem with restricted pairs.
cites work: A new fixed point approach for stable networks and stable marriages
cites work: Characterization of stable matchings as extreme points of a polytope
cites work: Network flow and 2-satisfiability
cites work: Efficient algorithms for generalized stable marriage and roommates problems
cites work: The Stable Roommates Problem with Ties
cites work: On-line algorithms for weighted bipartite matching and stable marriages
cites work: An improved approximation lower bound for finding almost stable maximum matchings
cites work: Size versus stability in the marriage problem
cites work: Approximation and Online Algorithms
cites work: ``Almost stable'' matchings in the roommates problem with bounded preference lists
cites work: Q5501851
cites work: The geometry of fractional stable matchings and its applications
cites work: Stable marriage with ties and bounded length preference lists
cites work: A necessary and sufficient condition for the existence of a complete stable matching
cites work: Q4198056
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Q3002782
cites work: Some simplified NP-complete graph problems
cites work: A maximum stable matching for the roommates problem
cites work: A new solution concept for the roommate problem: \(\mathcal{Q}\)-stable matchings
cites work: Socially Stable Matchings in the Hospitals/Residents Problem
DOI: 10.1016/J.DISOPT.2016.03.002
description: scientific article; zbMATH DE number 6872082