Lower Bounds for the Stable Marriage Problem and Its Variants

DOI10.1137/0219004MaRDI QIDQ3474282zbMATH OpenOpenAlexFDO

Authors Cheng Ng, Daniel S. Hirschberg

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://escholarship.org/uc/item/82n213qg

zbMATH Keywords

analysis of algorithmslower boundsstable marriage problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Operations research and management science (90B99)

Recommendations

• A Stable Marriage Requires Communication
• A stable marriage requires communication
• An efficient algorithm for the “stable roommates” problem
• Stable marriage and indifference
• On likely solutions of a stable marriage problem

Cited in

(18)

• Three Fast Algorithms for Four Problems in Stable Marriage
• The diameter of the stable marriage polytope: bounding from below
• A formal theory for the complexity class associated with the stable marriage problem
• The stable fixtures problem -- a many-to-many extension of stable roommates
• The stable marriage problem with restricted pairs.
• Worst-case choice for the stable marriage problem
• A stable marriage requires communication
• Lazy Gale-Shapley for many-to-one matching with partial information
• The complexity of the certification of properties of stable marriage
• Stable marriage and indifference
• Efficient algorithms for generalized stable marriage and roommates problems
• An efficient algorithm for batch stability testing
• Stable marriage with covering constraints -- a complete computational trichotomy
• Parametric stable marriage and minimum cuts
• Two algorithms for the student-project allocation problem
• Of Stable Marriages and Graphs, and Strategy and Polytopes
• On the stable \(b\)-matching problem in multigraphs
• Comment on worst-case choice for the stable marriage problem

This page was built for publication: Lower Bounds for the Stable Marriage Problem and Its Variants

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