Approximation Algorithms for the Sex-Equal Stable Marriage Problem

DOI10.1007/978-3-540-73951-7_18zbMath1209.68643OpenAlexW1734194907MaRDI QIDQ3603527

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)

Related Items (10)

Improved approximation algorithms for two variants of the stable marriage problem with ties ⋮ Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas ⋮ On the approximability of the stable matching problem with ties of size two ⋮ Linear time local approximation algorithm for maximum stable marriage ⋮ Faster and simpler approximation of stable matchings ⋮ Stable marriage with general preferences ⋮ A 25/17-approximation algorithm for the stable marriage problem with one-sided ties ⋮ Better and simpler approximation algorithms for the stable marriage problem ⋮ From Marriages to Coalitions: A Soft CSP Approach ⋮ Maximum stable matching with one-sided ties of bounded length

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