Рандомизированный распределенный адаптивный алгоритм решения задачи о максимальном потоке

Николай Владимирович Мальковский

Николай Владимирович Мальковский СПбГУ, Санкт-Петербург, Россия

Ключевые слова: оптимизация с ограничениями, градиентный спуск, распределенные алгоритмы, рандомизированные алгоритмы, стохастическая аппроксимация, задача о максимальном потоке

Аннотация

В этой статье предлагается метод решения одной из классических задач оптимизации — задачи о максимальном потоке. Алгоритм основан на общей процедуре балансирования дуг и не дает выигрыша по времени работы относительно существующих методов, однако обладает другими полезными свойствами: простую реализацию на распределенных вычислительных системах, сохранение близости к оптимальному решению при изменении параметров сети во времени. Рассматривается два варианта алгоритма: рандомизированный и синхронный. Рандомизированная
версия использует идеи покоординатного градиентного спуска и рандомизированных алгоритмов стохастической аппроксимации. Рандомизированная версия оказывается предпочтительней, так как имеет такой же порядок сходимости (экспоненциальный), но при этом устойчива к помехам и допускает более простую распределенную реализацию по сравнению с синхронной версией.

Биография автора

Николай Владимирович Мальковский, СПбГУ, Санкт-Петербург, Россия

Мальковский Н. В.: Магистрант математико-механического факультета СПбГУ.

Литература

[1] A. Goldberg and R. Tarjan, “Efficient maximum flow algorithms” Communications of the ACM, vol. 57, no. 8, 2014, pp. 82–89; doi: 10.1145/2628036
[2] R. Tarjan, J. Ward, B. Zhang, Y. Zhou, and J. Mao, “Balancing applied to maximum network flow problems” in Algorithms – ESA 2006. ESA 2006. Lecture Notes in Computer Science, vol. 4168, Y. Azar T. and Erlebach eds., Springer, 2006, pp. 612–623; doi: 10.1007/11841036_55
[3] E. C. Levitin and B. T. Polyak, “Metody minimizatsii pri nalichii ogranichenii” [Methods of minimization in the presence of constraints], Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki, vol. 6, no. 5, 1966, pp. 787–823.
[4] O. N. Granichin, “Poiskovye algoritmy stokhasticheskoi approksimatsii s randomizatsiei na vkhode” [Stochastic approximation search algorithms with randomization at the input], Avtomatika i Telemekhanika, no. 5, 2015, pp. 43-59; doi: 10.1134/S0005117915050033
[5] O. Granichin, V. Volkovich, D. Toledano-Kitai, Randomized algorithms in automatic control and data mining, Springer, 2014.
[6] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip algorithms,” IEEE Transactions on Information Theory, vol. 52, no. 6, 2006, pp. 2508–2530; doi: 10.1109/TIT.2006.874516
[7] R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Transactions on Automatic Control, vol. 49, no. 9, 2004, pp. 1520–1533; doi: 10.1109/TAC.2004.834113