Linear time local approximation algorithm for maximum stable marriage

DOI10.3390/a6030471zbMath1461.68257MaRDI QIDQ1736578

Zoltán Király

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a6030471

zbMATH Keywords

approximation; hospitals/residents problem; stable marriage; Gale-Shapley algorithm

Mathematics Subject Classification ID

91B26: Auctions, bargaining, bidding and selling, and other market models

68W25: Approximation algorithms

91B68: Matching models

Related Items

On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), A 3 / 2 -approximation Algorithm for the Student-Project Allocation Problem, Maximum stable matching with one-sided ties of bounded length, Hardness and approximation results for some variants of stable marriage problem, Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas, Characterization of super-stable matchings, Improved approximation algorithms for two variants of the stable marriage problem with ties, Linear time local approximation algorithm for maximum stable marriage, Editorial: Special issue on matching under preferences, Mathematical models for stable matching problems with ties and incomplete lists, Matching with indifferences: a comparison of algorithms in the context of course allocation, On the approximability of the stable matching problem with ties of size two

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Better and simpler approximation algorithms for the stable marriage problem
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Approximability results for stable marriage problems with ties.
• Hard variants of stable marriage.
• Linear time local approximation algorithm for maximum stable marriage
• Randomized approximation of the stable marriage problem
• Faster and Simpler Approximation of Stable Matchings
• Better and Simpler Approximation Algorithms for the Stable Marriage Problem
• Improved approximation results for the stable marriage problem
• A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
• Approximation Algorithms for the Sex-Equal Stable Marriage Problem
• A 3/2-Approximation Algorithm for General Stable Marriage
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Finding large stable matchings
• College Admissions and the Stability of Marriage