1. На главную
  2. Электронные версии
  3. Журнал вычислительной математики и математической физики
  4. T. 63, № 8, 2023

Журнал вычислительной математики и математической физики, 2023, T. 63, № 8, стр. 1395-1412

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

А. В. Карзанов 1, *

1 ЦЭМИ РАН
117418 Москва, Нахимовский пр-т, 47, Россия

* E-mail: akarzanov7@gmail.com

Поступила в редакцию 16.02.2023
После доработки 16.02.2023
Принята к публикации 28.04.2023

Аннотация

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

Ключевые слова: стабильный матчинг, посет ротаций, стабильный матчинг минимальной стоимости, медианный стабильный матчинг.

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

  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.

Дополнительные материалы отсутствуют.

Инструменты

предыдущая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал