Approximation Algorithms for the Sex-Equal Stable Marriage Problem

DOI10.1007/978-3-540-73951-7_18MaRDI QIDQ3603527zbMATH OpenOpenAlexFDO

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

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)

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

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
• Improved approximation algorithms for two variants of the stable marriage problem with ties
• Progress in Cryptology - INDOCRYPT 2004
• 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
• Stable marriage with general preferences
• Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case
• 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)