Email this article On the Set of Stable Matchings in a Bipartite Graph
- Authors: Karzanov A.V.1
-
Affiliations:
- Central Institute of Economics and Mathematics, Russian Academy of Sciences
- Issue: Vol 63, No 8 (2023)
- Pages: 1395-1412
- Section: ИНФОРМАТИКА
- URL: https://journals.rcsi.science/0044-4669/article/view/136218
- DOI: https://doi.org/10.31857/S0044466923080082
- EDN: https://elibrary.ru/WSLYAY
- ID: 136218
Cite item
Open Access
Access granted
Subscription Access
Abstract
The topic of stable matchings (marriages) in bipartite graphs gained popularity beginning from the appearance of the classical Gale and Shapley work. In this paper, a detailed review of selected and other related statements in this field that describe structured, polyhedral, and algorithmic properties of such objects and their sets accompanied by short proofs is given.
About the authors
A. V. Karzanov
Central Institute of Economics and Mathematics, Russian Academy of Sciences
Author for correspondence.
Email: akarzanov7@gmail.com
117418, Moscow, Russia
References
- Gale D., Shapley L.S. College admissions and the stability of marriage // Amer. Math. Monthly. 1962. V. 69. № 1. P. 9–15.
- Irving R.W. An efficient algorithm for the “stable roommates” problem // J. Algorithms. 1985. V. 6. P. 577–595.
- Tan J. A necessary and sufficient condition for the existence of a complete stable matching // J. Algorithms. 1991. V. 12. P. 154–178.
- Baiou M., Balinski M. Erratum: the stable allocation (or ordinal transportation) problem // Math. Oper. Res. 2002. V. 27. № 4. P. 662–680.
- Irving R.W., Leather P. The complexity of counting stable marriages // SIAM J. Comput. 1986. V. 15. P. 655–667.
- McVitie D., Wilson L.B. The stable marriage problem // Commun. ACM. 1971. V. 14. P. 486–492.
- Irving R.W., Leather P., Gusfield D. An efficient algorithm for the optimal stable marriage problem // J. ACM. 1987. V. 34. P. 532–543.
- Picard J. Maximum closure of a graph and applications to combinatorial problems // Manage. Sci. 1976. V. 22. P. 1268–1272.
- Vande Vate J.H. Linear programming brings marital bliss // Oper. Res. Lett. 1989. V. 8. P. 147–153.
- Teo C.P., Sethuraman J. The geometry of fractional stable matchings and its applications // Math. Oper. Res. 1998. V. 23. № 4. P. 874–891.
- Knuth D.E. Mariages stables. Les Presses de l’Université de Montreal. Montreal, 1976.
- Schrijver A. Combinatorial Optimization. Vol. A. Springer, 2003.
- McVitie D., Wilson L.B. Stable marriage assignments for unequal sets // BIT. 1970. V. 10. P. 295–309.
- Dean B.C., Munshi S. Faster algorithms for stable allocation problems // Algorithmica. 2010. V. 58. № 1. P. 59–81.
- Mourtos I., Samaris M. Stable allocations and partially ordered sets // Discr. Optimiz. 2022. V. 46. P. 100731.
- Gusfield D. Three fast algorithms for four problems in stable marriage // SIAM J. Comput. 1987. V. 16. P. 111–128.
- Polya G., Tarjan R.E., Woods D.R. Notes on Introductory Combinatorics. Birkbauser Verlag, Boston, Mass., 1983.
- Tardos È. A strongly polynomial algorithm to solve combinatorial linear problems // Oper. Research. 1986. V. 34. P. 250–256.
- Карзанов А.В. О замкнутых множествах ориентированного графа // Ж. вычисл. матем. и матем. физ. 1984. Т. 24. С. 1903–1906.
- Rothblum U.G. Characterization of stable matchings as extreme points of a polytope // Math. Programming. 1992. V. 54. P. 57–67.
- Roth A.E., Rothblum U.G., Vande Vate J.H. Stable matching, optimal assignments and linear programming // Math. Oper. Res. 1993. V. 18. P. 808–828.
- Valiant L.G. The complexity of computing the permanent // Theoret. Comp. Sci. 1979. V. 8. P. 189–201.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
- Provan J.S., Ball M.O. The complexity of counting cuts and of computing the probability that a graph is connected // SIAM J. Comput. 1983. V. 12. P. 777–788.
Supplementary files
