Maximum stable matching with one-sided ties of bounded length
From MaRDI portal
Publication:5918705
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
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