Approximation Algorithms for the Sex-Equal Stable Marriage Problem

DOI10.1007/978-3-540-73951-7_18zbMATH Open1209.68643OpenAlexW1734194907MaRDI QIDQ3603527FDOQ3603527

Authors: Shuichi Miyazaki, Hiroki Yanagisawa, Kazuo Iwama 

Publication date: 17 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73951-7_18

Recommendations

• Approximation algorithms for the sex-equal stable marriage problem
• Sex-equal stable matchings: complexity and exact algorithms
• Complexity of the sex-equal stable marriage problem
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
• ``Sex-equal stable matchings

zbMATH Keywords

approximation algorithmsstable marriage problemsex-equal stable marriage problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Matching models (91B68)

Cited In (18)

• Complexity of the sex-equal stable marriage problem
• Faster and simpler approximation of stable matchings
• Linear time local approximation algorithm for maximum stable marriage
• Maximum stable matching with one-sided ties of bounded length
• Better and simpler approximation algorithms for the stable marriage problem
• Parametric stable marriage and minimum cuts
• Progress in Cryptology - INDOCRYPT 2004
• Improved approximation algorithms for two variants of the stable marriage problem with ties
• Approximation algorithms for the sex-equal stable marriage problem
• Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas
• Algorithms for new types of fair stable matchings
• From Marriages to Coalitions: A Soft CSP Approach
• Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case
• Stable marriage with general preferences
• On the approximability of the stable matching problem with ties of size two
• ``Sex-equal stable matchings
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• Sex-equal stable matchings: complexity and exact algorithms

This page was built for publication: Approximation Algorithms for the Sex-Equal Stable Marriage Problem

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