A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
From MaRDI portal
Publication:528863
DOI10.1007/s00453-012-9699-2zbMath1360.68904OpenAlexW1986927971MaRDI QIDQ528863
Kazuo Iwama, Hiroki Yanagisawa, Shuichi Miyazaki
Publication date: 17 May 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2433/226941
approximation algorithminteger programstable marriage problemintegrality gaplinear program relaxationstable marriage with ties and incomplete lists
Related Items (5)
Characterization of super-stable matchings ⋮ Improved approximation algorithms for two variants of the stable marriage problem with ties ⋮ On the approximability of the stable matching problem with ties of size two ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ Maximum stable matching with one-sided ties of bounded length
Cites Work
- Better and simpler approximation algorithms for the stable marriage problem
- A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
- Stable marriage with ties and bounded length preference lists
- Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
- Some remarks on the stable matching problem
- Stable marriage and indifference
- Hard variants of stable marriage.
- Randomized approximation of the stable marriage problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- The Geometry of Fractional Stable Matchings and Its Applications
- 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
- Stable Matchings, Optimal Assignments, and Linear Programming
- College Admissions and the Stability of Marriage
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
