A 25/17-approximation algorithm for the stable marriage problem with one-sided ties

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

zbMATH Keywords

approximation algorithminteger programstable marriage problemintegrality gaplinear program relaxationstable marriage with ties and incomplete lists

Mathematics Subject Classification ID

Integer programming (90C10) Approximation algorithms (68W25) Matching models (91B68)

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

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

This page was built for publication: A 25/17-approximation algorithm for the stable marriage problem with one-sided ties