A 3/2-Approximation Algorithm for General Stable Marriage
From MaRDI portal
Publication:3638073
DOI10.1007/978-3-642-02927-1_57zbMath1248.68564OpenAlexW1563534733MaRDI QIDQ3638073
Publication date: 14 July 2009
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02927-1_57
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (20)
Characterization of super-stable matchings ⋮ On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Improved approximation algorithms for two variants of the stable marriage problem with ties ⋮ Pareto stability in two-sided many-to-many matching with weak preferences ⋮ On the number of employed in the matching model ⋮ On the approximability of the stable matching problem with ties of size two ⋮ Parameterized algorithms for stable matching with ties and incomplete lists ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ Maximum locally stable matchings ⋮ Linear time local approximation algorithm for maximum stable marriage ⋮ Local search approaches in stable matching problems ⋮ Faster and simpler approximation of stable matchings ⋮ Mathematical models for stable matching problems with ties and incomplete lists ⋮ 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 ⋮ Unnamed Item ⋮ Maximum stable matching with one-sided ties of bounded length ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
This page was built for publication: A 3/2-Approximation Algorithm for General Stable Marriage
