Approximation algorithms for the sex-equal stable marriage problem

DOI10.1145/1868237.1868239MaRDI QIDQ3188983zbMATH OpenOpenAlexFDO

Authors Shuichi Miyazaki, Hiroki Yanagisawa, Kazuo Iwama

Publication date 9 September 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2433/226949

zbMATH Keywords

approximation algorithmssex-equal stable marriage problemstable marriage problem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) 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
• Hard variants of stable marriage.

Cited in

(12)

• The stable marriage problem: an interdisciplinary review from the physicist's perspective
• Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case
• Submodular reassignment problem for reallocating agents to tasks with synergy effects
• Approximation Algorithms for the Sex-Equal Stable Marriage Problem
• Solving stable matching problems using answer set programming
• On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
• Sex-equal stable matchings: complexity and exact algorithms
• Progress in Cryptology - INDOCRYPT 2004
• ``Sex-equal stable matchings
• Algorithms for new types of fair stable matchings
• Complexity of the sex-equal stable marriage problem
• 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 Q3188983)