Size Versus Stability in the Marriage Problem

DOI10.1007/978-3-540-93980-1_2zbMath1209.68266OpenAlexW4234305216MaRDI QIDQ3602826

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

Publication date: 12 February 2009

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: http://eprints.gla.ac.uk/5930/1/minbp.pdf

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Related Items (2)

Almost stable matchings by truncating the Gale-Shapley algorithm ⋮ An improved approximation lower bound for finding almost stable maximum matchings

Cites Work

• Pairwise kidney exchange
• Two algorithms for the student-project allocation problem
• Size versus stability in the marriage problem
• 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 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Size Versus Stability in the Marriage Problem