Geometric stable roommates

DOI10.1016/j.ipl.2008.10.003zbMath1191.68753OpenAlexW1996160681MaRDI QIDQ976079

Joseph S. B. Mitchell, Alon Efrat, Kazuya Okamoto, Esther M. Arkin, Sang Won Bae, Valentin Polishchuk

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.10.003

zbMATH Keywords

algorithmsgraph algorithmscomputational geometry\(\alpha \)-stable matchingconsistent preferencesstable roommates with ties

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The Price of Matching with Metric Preferences, Allocating group housing, Stable matching with network externalities, The three-dimensional stable roommates problem with additively separable preferences, Subquadratic algorithms for succinct stable matching, Two hardness results for core stability in hedonic coalition formation games, A General Framework for Stable Roommates Problems using Answer Set Programming, Mathematical models for stable matching problems with ties and incomplete lists, Stable roommates spanner, On the convergence of swap dynamics to Pareto-optimal matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Über Treffanzahlen bei translationsgleichen Eikörpern
• The stable marriage problem with master preference lists
• An optimal algorithm for closest-pair maintenance
• Stable matchings in three-sided systems with cyclic preferences
• Stable matching with preferences derived from a psychological model
• Maximum matchings in planar graphs via Gaussian elimination
• The Stable Roommates Problem with Ties
• Three-Dimensional Stabl Matching Problems
• NP-complete stable matching problems
• Two’s Company, Three’s a Crowd: Stable Family and Threesome Roommates Problems
• An efficient algorithm for the “stable roommates” problem
• A New Approach to Stable Matching Problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Three-dimensional stable matching with cyclic preferences
• College Admissions and the Stability of Marriage