scientific article; zbMATH DE number 1962834

MaRDI QIDQ4418671zbMATH OpenFDO

Authors Robert W. Irving, David F. Manlove, Sandy Scott

Publication date 11 August 2003

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2607/26070439.htm

zbMATH Keywords

hospitals/residents problemlower boundNP-completenesspolynomial-time algorithmstable matching problemstrong stability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Combinatorial optimization (90C27)

Recommendations

• Strongly stable matchings in time \(O(nm)\) and extension to the hospitals-residents problem
• STACS 2004
• scientific article; zbMATH DE number 1617265
• The strongly stable roommates problem
• An algorithm for strong stability in the student-project allocation problem with ties

Cited in

(31)

• The stable marriage problem with master preference lists
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Equivalence of two-sided stable matching
• Three-sided stable matching problem with two of them as cooperative partners
• Strongly stable and maximum weakly stable noncrossing matchings
• Improving solution times for stable matching problems through preprocessing
• The stable marriage problem: an interdisciplinary review from the physicist's perspective
• Two problems in max-size popular matchings
• Revisiting two-sided stability constraints
• Strongly stable matchings in time \(O(nm)\) and extension to the hospitals-residents problem
• The Hospitals/Residents Problem with Quota Lower Bounds
• Stable matchings with ties, master preference lists, and matroid constraints
• Pareto optimality in the kidney exchange Problem
• Strongly stable and maximum weakly stable noncrossing matchings
• Stable marriage with general preferences
• Pairwise Preferences in the Stable Marriage Problem
• Popular matchings with multiple partners
• Bribery and control in stable marriage
• Pareto stable matchings under one-sided matroid constraints
• STACS 2004
• Super-stability in the student-project allocation problem with ties
• Balancing stability and efficiency in team formation as a generalized roommate problem
• Effective data reduction for strongly stable matching in very sparse graphs
• Strongly stable matchings under matroid constraints
• Perfect matchings and popularity in the many-to-many setting
• The strongly stable matching problem with closures
• The strong core of housing markets with partial order preferences
• The stable marriage problem with ties and restricted edges
• Two algorithms for the student-project allocation problem
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
• Efficient algorithms for generalized stable marriage and roommates problems

This page was built for publication:

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