О стабильных потоках и предпотоках

Обложка

Цитировать

Полный текст

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

Аннотация

Предлагается новый алгоритм построения стабильного потока в сети с несколькими источниками и стоками. Он основан на идее предпотоков (примененной в 1970-х годах для более быстрого решения классической задачи о максимальном потоке) и имеет временнýю сложность \(O(nm)\) для сети с \(n\) вершинами и \(m\) ребрами. Полученные результаты затем распространяются на более широкий класс объектов – т.н. стабильные квазипотоки с ограниченными отклонениями от балансовых соотношений в нетерминальных вершинах. Библ. 12.

Об авторах

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

ЦЭМИ РАН

Автор, ответственный за переписку.
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. Dean B.C., Munshi S. Faster algorithms for stable allocation problems // Algorithmica. 2010. V. 58. № 1. P. 59–81.
  6. Sleator D.D., Tarjan R.E. A data structure for dynamic trees // J. Computer and System Sciences. 1983. V. 26. № 3. P. 362–391.
  7. Sleator D.D., Tarjan R.E. Self-adjusting binary search trees // J. ACM. 1985. V. 32. № 3. P. 652–686.
  8. Fleiner T. On stable matchings and flows // Algorithms. 2014. V. 7. P. 1–14.
  9. Ostrovsky M. Stability in supply chain networks // Amer. Econ. Rev. 2006. V. 98. P. 897–923.
  10. Cseh Á., Matuschke J. New and simple algorithms for stable flow problems // Algorithmica. 2019. V. 81. № 6. P. 2557–2591.
  11. Карзанов А.В. Нахождение максимального потока в сети методом предпотоков // Докл. АН СССР. 1974. Т. 215. С. 49–52. (English translation in: Soviet Math. Dokl. 1974. V. 15. № 2. P. 434–437.)
  12. Cseh Á., Matuschke J., Skutella M. Stable flows over time // Algorithms. 2013. V. 6. P. 532–545.

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

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

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