Approximability results for stable marriage problems with ties.

DOI10.1016/S0304-3975(03)00321-9zbMath1060.68085OpenAlexW2133312780MaRDI QIDQ1426466

David F. Manlove, Shuichi Miyazaki, Magnús M. Halldórsson, Sandy Scott, Kazuo Iwama, Robert W. Irving, Yasufumi Morita

Publication date: 14 March 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00321-9

zbMATH Keywords

Approximation algorithmTiesInapproximability resultsStable marriage problemUnacceptable partners

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (18)

On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Review of the theory of stable matchings and contract systems ⋮ Hardness and approximation results for some variants of stable marriage problem ⋮ Parameterized complexity and local search approaches for the stable marriage problem with ties ⋮ Better and Simpler Approximation Algorithms for the Stable Marriage Problem ⋮ A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem ⋮ How hard is it to satisfy (almost) all roommates ⋮ Linear time local approximation algorithm for maximum stable marriage ⋮ Local search approaches in stable matching problems ⋮ Faster and simpler approximation of stable matchings ⋮ Better and simpler approximation algorithms for the stable marriage problem ⋮ Efficient algorithms for generalized stable marriage and roommates problems ⋮ Student-project allocation with preferences over projects ⋮ The stable marriage problem with master preference lists ⋮ Maximum stable matching with one-sided ties of bounded length ⋮ Stable marriage with ties and bounded length preference lists ⋮ Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems ⋮ A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences

Cites Work

• Complexity of the sex-equal stable marriage problem
• Some remarks on the stable matching problem
• A new fixed point approach for stable networks and stable marriages
• Stable marriage and indifference
• Hard variants of stable marriage.
• Minimum Edge Dominating Sets
• NP-complete stable matching problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Three Fast Algorithms for Four Problems in Stable Marriage
• College Admissions and the Stability of Marriage
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximability results for stable marriage problems with ties.