On Stable Flows and Preflows

Capa

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Somente assinantes

Resumo

We propose a new algorithm of finding a stable flow in a network with several sources and sinks. It is based on the idea of preflows (applied in the 1970s for a faster solution of the classical maximal flow problem) and has time complexity  for a network with O(nm) vertices and m  edges. The obtained results are further generalized to a larger class of objects, the so-called stable quasi-flows with bounded deviations from the balanced relations in nonterminal vertices.

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. 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.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

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