Improved approximation algorithms for two variants of the stable marriage problem with ties
From MaRDI portal
Publication:896290
DOI10.1007/s10107-015-0923-0zbMath1411.91422MaRDI QIDQ896290
Chien-Chung Huang, Telikepalli Kavitha
Publication date: 9 December 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-015-0923-0
05C90: Applications of graph theory
68W25: Approximation algorithms
91B68: Matching models
91-04: Software, source code, etc. for problems pertaining to game theory, economics, and finance
Related Items
On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), Maximum stable matching with one-sided ties of bounded length, Three-sided matching problem with mixed preferences, On the approximability of the stable matching problem with ties of size two
Cites Work
- A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
- Better and simpler approximation algorithms for the stable marriage problem
- Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
- Some remarks on the stable matching problem
- Linear programming brings marital bliss
- Stable marriage and indifference
- Hard variants of stable marriage.
- Linear time local approximation algorithm for maximum stable marriage
- Randomized approximation of the stable marriage problem
- Socially Stable Matchings in the Hospitals/Residents Problem
- Faster and Simpler Approximation of Stable Matchings
- Improved approximation results for the stable marriage problem
- Approximation Algorithms for the Sex-Equal Stable Marriage Problem
- A 3/2-Approximation Algorithm for General Stable Marriage
- Algorithmics of Matching Under Preferences
- College Admissions and the Stability of Marriage
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
