An algorithm for the maximum weight strongly stable matching problem

DOI10.4230/LIPICS.ISAAC.2018.42MaRDI QIDQ5091034zbMATH OpenFDO

Authors Adam Kunysz

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2018.42

zbMATH Keywords

rotationstable marriageweighted matchingstrongly stable matching

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Strongly stable matchings in time \(O(nm)\) and extension to the hospitals-residents problem
• STACS 2004
• Characterisation of strongly stable matchings
• The strongly stable roommates problem
• A faster algorithm for the Strongly Stable b-Matching Problem

Cites work

• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 1405659 (Why is no real title available?)
• A 3/2-Approximation Algorithm for General Stable Marriage
• A data structure for dynamic trees
• A new fixed point approach for stable networks and stable marriages
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• Better and simpler approximation algorithms for the stable marriage problem
• Characterisation of strongly stable matchings
• Characterization of stable matchings as extreme points of a polytope
• College Admissions and the Stability of Marriage
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Efficient algorithms for generalized stable marriage and roommates problems
• Faster Scaling Algorithms for Network Problems
• Faster and simpler approximation of stable matchings
• Hard variants of stable marriage.
• Linear programming brings marital bliss
• Network flow and 2-satisfiability
• Stable Matchings, Optimal Assignments, and Linear Programming
• Stable marriage and indifference
• Strongly stable matchings in time \(O(nm)\) and extension to the hospitals-residents problem
• The geometry of fractional stable matchings and its applications
• The strongly stable roommates problem
• The structure of stable marriage with indifference

Cited in

(10)

• Strongly stable matchings under matroid constraints
• The Maximum-Weight Stable Matching Problem: Duality and Efficiency
• Core and stability notions in many-to-one matching markets with indifferences
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2
• Adapting stable matchings to forced and forbidden pairs
• Ex-post stability under two-sided matching: complexity and characterization
• The stable marriage problem with ties and restricted edges
• The strongly stable matching problem with closures
• Marriage market with indifferences: a linear programming approach

This page was built for publication: An algorithm for the maximum weight strongly stable matching problem

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