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 algorithmssex-equal stable marriage problemstable marriage problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27) 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)

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

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)