On the Set of Stable Matchings in a Bipartite Graph

Capa

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Acesso é pago ou somente para assinantes

Resumo

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.

Sobre autores

A. Karzanov

Central Institute of Economics and Mathematics, Russian Academy of Sciences

Autor responsável pela correspondência
Email: akarzanov7@gmail.com
117418, Moscow, Russia

Bibliografia

  1. Gale D., Shapley L.S. College admissions and the stability of marriage // Amer. Math. Monthly. 1962. V. 69. № 1. P. 9–15.
  2. Irving R.W. An efficient algorithm for the “stable roommates” problem // J. Algorithms. 1985. V. 6. P. 577–595.
  3. Tan J. A necessary and sufficient condition for the existence of a complete stable matching // J. Algorithms. 1991. V. 12. P. 154–178.
  4. Baiou M., Balinski M. Erratum: the stable allocation (or ordinal transportation) problem // Math. Oper. Res. 2002. V. 27. № 4. P. 662–680.
  5. Irving R.W., Leather P. The complexity of counting stable marriages // SIAM J. Comput. 1986. V. 15. P. 655–667.
  6. McVitie D., Wilson L.B. The stable marriage problem // Commun. ACM. 1971. V. 14. P. 486–492.
  7. Irving R.W., Leather P., Gusfield D. An efficient algorithm for the optimal stable marriage problem // J. ACM. 1987. V. 34. P. 532–543.
  8. Picard J. Maximum closure of a graph and applications to combinatorial problems // Manage. Sci. 1976. V. 22. P. 1268–1272.
  9. Vande Vate J.H. Linear programming brings marital bliss // Oper. Res. Lett. 1989. V. 8. P. 147–153.
  10. Teo C.P., Sethuraman J. The geometry of fractional stable matchings and its applications // Math. Oper. Res. 1998. V. 23. № 4. P. 874–891.
  11. Knuth D.E. Mariages stables. Les Presses de l’Université de Montreal. Montreal, 1976.
  12. Schrijver A. Combinatorial Optimization. Vol. A. Springer, 2003.
  13. McVitie D., Wilson L.B. Stable marriage assignments for unequal sets // BIT. 1970. V. 10. P. 295–309.
  14. Dean B.C., Munshi S. Faster algorithms for stable allocation problems // Algorithmica. 2010. V. 58. № 1. P. 59–81.
  15. Mourtos I., Samaris M. Stable allocations and partially ordered sets // Discr. Optimiz. 2022. V. 46. P. 100731.
  16. Gusfield D. Three fast algorithms for four problems in stable marriage // SIAM J. Comput. 1987. V. 16. P. 111–128.
  17. Polya G., Tarjan R.E., Woods D.R. Notes on Introductory Combinatorics. Birkbauser Verlag, Boston, Mass., 1983.
  18. Tardos È. A strongly polynomial algorithm to solve combinatorial linear problems // Oper. Research. 1986. V. 34. P. 250–256.
  19. Карзанов А.В. О замкнутых множествах ориентированного графа // Ж. вычисл. матем. и матем. физ. 1984. Т. 24. С. 1903–1906.
  20. Rothblum U.G. Characterization of stable matchings as extreme points of a polytope // Math. Programming. 1992. V. 54. P. 57–67.
  21. 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.
  22. Valiant L.G. The complexity of computing the permanent // Theoret. Comp. Sci. 1979. V. 8. P. 189–201.
  23. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  24. 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.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar
2.

Baixar (17KB)
Metadados
3.

Baixar (20KB)
Metadados
4.

Baixar (50KB)
Metadados

Declaração de direitos autorais © А.В. Карзанов, 2023