scientific article; zbMATH DE number 2086256

MaRDI QIDQ3044355zbMATH OpenFDO

Authors Magnús M. Halldórsson, Shuichi Miyazaki, Yasufumi Morita, Kazuo Iwama

Publication date 11 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2286/22860554.htm

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Recommendations

• Hard variants of stable marriage.
• Approximability results for stable marriage problems with ties.
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• scientific article; zbMATH DE number 1405659
• Improved approximation of the stable marriage problem

Cited in

(18)

• The stable marriage problem with master preference lists
• Stable marriage with ties and bounded length preference lists
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Comment on worst-case choice for the stable marriage problem
• Approximability results for stable marriage problems with ties.
• Hard variants of stable marriage.
• Randomized approximation of the stable marriage problem
• A nonconstructive elementary proof of the existence of stable marriages
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Stable fractional matchings
• Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case
• Some hard stable marriage problems: a survey on multivariate analysis
• Size Versus Stability in the Marriage Problem
• On the complexity of stable fractional hypergraph matching
• On the complexity of distributed stable matching with small messages
• Complexity of the sex-equal stable marriage problem
• Hardness results on the man-exchange stable marriage problem with short preference lists
• Size versus stability in the marriage problem

This page was built for publication:

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