О множестве стабильных матчингов двудольного графа

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Тема стабильных матчингов (марьяжей) в двудольных графах приобрела широкую популярность, начиная с выхода классической работы Гейла и Шепли. В настоящей работе дается развернутый обзор избранных и взаимосвязанных утверждений в этой области, описывающих структурные, полиэдральные и алгоритмические свойства таких объектов и их множеств, снабжая эти утверждения короткими доказательствами. Библ. 24. Фиг. 3.

Об авторах

А. В. Карзанов

ЦЭМИ РАН

Автор, ответственный за переписку.
Email: akarzanov7@gmail.com
Россия, 117418, Москва, Нахимовский пр-т, 47

Список литературы

  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.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать
2.

Скачать (17KB)
Метаданные
3.

Скачать (20KB)
Метаданные
4.

Скачать (50KB)
Метаданные

© А.В. Карзанов, 2023