Improved approximation algorithms for two variants of the stable marriage problem with ties
DOI10.1007/S10107-015-0923-0zbMATH Open1411.91422OpenAlexW881461489MaRDI QIDQ896290FDOQ896290
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
Recommendations
- An improved approximation algorithm for the stable marriage problem with one-sided ties
- Improved approximation of the stable marriage problem
- A \(1.875\)-approximation algorithm for the stable marriage problem
- Improved approximation results for the stable marriage problem
- Better and simpler approximation algorithms for the stable marriage problem
Applications of graph theory (05C90) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Approximation algorithms (68W25) Matching models (91B68)
Cites Work
- Some remarks on the stable matching problem
- Improved approximation results for the stable marriage problem
- Title not available (Why is that?)
- College Admissions and the Stability of Marriage
- Algorithmics of Matching Under Preferences
- Linear programming brings marital bliss
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
- Better and simpler approximation algorithms for the stable marriage problem
- Hard variants of stable marriage.
- Stable marriage and indifference
- Approximation Algorithms for the Sex-Equal Stable Marriage Problem
- A 3/2-Approximation Algorithm for General Stable Marriage
- Randomized approximation of the stable marriage problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
- Socially Stable Matchings in the Hospitals/Residents Problem
- Linear time local approximation algorithm for maximum stable marriage
- Faster and Simpler Approximation of Stable Matchings
Cited In (7)
- Three-sided matching problem with mixed preferences
- Maximum stable matching with one-sided ties of bounded length
- On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization)
- Critical Relaxed Stable Matchings with Two-Sided Ties
- On the approximability of the stable matching problem with ties of size two
- Stable matchings, one-sided ties, and approximate popularity
- Algorithms and Computation
This page was built for publication: Improved approximation algorithms for two variants of the stable marriage problem with ties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896290)
