A Stable Marriage Requires Communication

DOI10.1137/1.9781611973730.68zbMath1372.68125OpenAlexW1584715278MaRDI QIDQ5363098

Will Rosenbaum, Yannai A. Gonczarowski, Rafail Ostrovsky, Noam Nisan

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.68

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Related Items (3)

Stable matching mechanisms are not obviously strategy-proof ⋮ Subquadratic algorithms for succinct stable matching ⋮ A stable marriage requires communication

This page was built for publication: A Stable Marriage Requires Communication