Maximum stable matching with one-sided ties of bounded length

DOI10.1007/s00224-022-10072-1zbMath1489.68401OpenAlexW4280581864MaRDI QIDQ5918705

Chi-Kit Lam, C. Gregory Plaxton

Publication date: 21 June 2022

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-022-10072-1

zbMATH Keywords

approximation algorithmstable matchingintegrality gap

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Matching models (91B68)

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
• A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems
• Improved approximation algorithms for two variants of the stable marriage problem with ties
• The stable marriage problem with master preference lists
• Stable marriage with ties and bounded length preference lists
• Some remarks on the stable matching problem
• Linear programming brings marital bliss
• Characterization of stable matchings as extreme points of a polytope
• Stable marriage and indifference
• Approximability results for stable marriage problems with ties.
• Hard variants of stable marriage.
• Linear time local approximation algorithm for maximum stable marriage
• Faster and simpler approximation of stable matchings
• Randomized approximation of the stable marriage problem
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• On the approximability of the stable matching problem with ties of size two
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• AdWords and generalized online matching
• 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
• A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists
• A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties
• Online bipartite matching with random arrivals
• College Admissions and the Stability of Marriage
• Maximum stable matching with one-sided ties of bounded length
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Maximum stable matching with one-sided ties of bounded length