Improved approximation algorithms for two variants of the stable marriage problem with ties

DOI10.1007/s10107-015-0923-0zbMath1411.91422OpenAlexW881461489MaRDI 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

zbMATH Keywords

approximation algorithmsstable matching

Mathematics Subject Classification ID

Applications of graph theory (05C90) Approximation algorithms (68W25) Matching models (91B68) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)

Related Items (4)

On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ On the approximability of the stable matching problem with ties of size two ⋮ Maximum stable matching with one-sided ties of bounded length ⋮ Three-sided matching problem with mixed preferences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Improved approximation algorithms for two variants of the stable marriage problem with ties