A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
From MaRDI portal
Publication:528863
DOI10.1007/S00453-012-9699-2zbMATH Open1360.68904OpenAlexW1986927971MaRDI QIDQ528863FDOQ528863
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 algorithmintegrality gapstable marriage probleminteger programlinear program relaxationstable marriage with ties and incomplete lists
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
Cited In (7)
- Characterization of super-stable matchings
- Maximum stable matching with one-sided ties of bounded length
- 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)
