Characterization of super-stable matchings

DOI10.1007/978-3-030-83508-8_35OpenAlexW3191400469MaRDI QIDQ832893

N. E. Zubov

Publication date: 25 March 2022

Full work available at URL: https://arxiv.org/abs/2105.09602

zbMATH Keywords

distributive latticematching polytopesuper-stable matching

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• Efficient algorithms for generalized stable marriage and roommates problems
• Linear programming brings marital bliss
• Characterization of stable matchings as extreme points of a polytope
• Stable marriage and indifference
• The structure of stable marriage with indifference
• Linear time local approximation algorithm for maximum stable marriage
• Faster and simpler approximation of stable matchings
• The set of super-stable marriages forms a distributive lattice
• Maintaining a topological order under edge insertions
• A faster algorithm for the Strongly Stable \(b\)-Matching Problem
• Rings of sets
• The Geometry of Fractional Stable Matchings and Its Applications
• Strongly stable matchings in time O ( nm ) and extension to the hospitals-residents problem
• A 3/2-Approximation Algorithm for General Stable Marriage
• Characterisation of Strongly Stable Matchings
• A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists
• An Improved Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties

This page was built for publication: Characterization of super-stable matchings