Approximability results for stable marriage problems with ties.
From MaRDI portal
Publication:1426466
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
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.
