Size versus stability in the marriage problem

DOI10.1016/j.tcs.2010.02.003zbMath1190.90155OpenAlexW2175150243MaRDI QIDQ964402

Shubham Mittal, David F. Manlove, Péter Biró

Publication date: 15 April 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.02.003

zbMATH Keywords

polynomial-time algorithmstable marriage problemstable matchingblocking pairblocking agentinapproximability result

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Matching models (91B68)

Related Items (27)

Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability ⋮ Constrained stable marriage with free edges or few blocking pairs ⋮ Popularity in the generalized hospital residents setting ⋮ Matching formulation of the staff transfer problem: meta-heuristic approaches ⋮ Computing relaxations for the three-dimensional stable matching problem with cyclic preferences ⋮ Stable marriage with groups of similar agents ⋮ Robust and approximately stable marriages under partial information ⋮ On the number of employed in the matching model ⋮ ``Almost-stable matchings in the hospitals/residents problem with couples ⋮ ``Almost stable matchings in the roommates problem with bounded preference lists ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ The stable roommates problem with short lists ⋮ How hard is it to satisfy (almost) all roommates ⋮ Application of pair approximation method to modeling and analysis of a marriage network ⋮ Maximum locally stable matchings ⋮ Local search approaches in stable matching problems ⋮ Strongly stable and maximum weakly stable noncrossing matchings ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ Size Versus Stability in the Marriage Problem ⋮ Complexity of finding Pareto-efficient allocations of highest welfare ⋮ The Stable Roommates Problem with Short Lists ⋮ (Un)stable matchings with blocking costs ⋮ MATCHING WITH COUPLES: A MULTIDISCIPLINARY SURVEY ⋮ Unnamed Item ⋮ Size versus fairness in the assignment problem ⋮ How Good Are Popular Matchings ⋮ The hospitals/residents problem with lower quotas

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pairwise kidney exchange
• An improved approximation lower bound for finding almost stable maximum matchings
• Some remarks on the stable matching problem
• On-line algorithms for weighted bipartite matching and stable marriages
• Hard variants of stable marriage.
• Instability of matchings in decentralized markets with various preference structures
• The Hospitals/Residents Problem with Quota Lower Bounds
• The Stable Roommates Problem with Ties
• Kidney Exchange
• NP-complete stable matching problems
• An efficient algorithm for the “stable roommates” problem
• The Complexity of Counting Stable Marriages
• Approximation and Online Algorithms
• College Admissions and the Stability of Marriage

This page was built for publication: Size versus stability in the marriage problem