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

DOI10.1007/S00453-012-9699-2zbMATH Open1360.68904OpenAlexW1986927971MaRDI QIDQ528863FDOQ528863

Authors: Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa 

Publication date: 17 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/226941

Recommendations

• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• An improved approximation algorithm for the stable marriage problem with one-sided ties
• A \(1.875\)-approximation algorithm for the stable marriage problem
• Algorithms and Computation
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem

zbMATH Keywords

approximation algorithmintegrality gapstable marriage probleminteger programlinear program relaxationstable marriage with ties and incomplete lists

Mathematics Subject Classification ID

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

Cites Work

• Some remarks on the stable matching problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Improved approximation results for the stable marriage problem
• Title not available (Why is that?)
• College Admissions and the Stability of Marriage
• The geometry of fractional stable matchings and its applications
• Title not available (Why is that?)
• Stable Matchings, Optimal Assignments, and Linear Programming
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Better and simpler approximation algorithms for the stable marriage problem
• Hard variants of stable marriage.
• Stable marriage and indifference
• Approximation Algorithms for the Sex-Equal Stable Marriage Problem
• A 3/2-Approximation Algorithm for General Stable Marriage
• Stable marriage with ties and bounded length preference lists
• Randomized approximation of the stable marriage problem
• A \(1.875\)-approximation algorithm for the stable marriage problem
• Title not available (Why is that?)
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem

Cited In (11)

• Characterization of super-stable matchings
• A tight approximation bound for the stable marriage problem with restricted ties
• Maximum stable matching with one-sided ties of bounded length
• An improved approximation algorithm for the stable marriage problem with one-sided ties
• A \((1 + 1/e)\)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• Improved approximation algorithms for two variants of the stable marriage problem with ties
• Critical Relaxed Stable Matchings with Two-Sided Ties
• The stable marriage problem: an interdisciplinary review from the physicist's perspective
• On the approximability of the stable matching problem with ties of size two
• Stable matchings, one-sided ties, and approximate popularity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528863)