Randomized Distributed Adaptive Algorithm for a Maximum Flow Problem
Abstract
This paper presents an algorithm for solving one of the fundamental optimization problems — maximum flow problem. The algorithm is based on the ideas of arc balancing procedure and projected gradient method. Although the algorithm does not improve asymptotic complexity over existing methods it still possess some usefull properties: natural implementation in distributed systems and convergence to an optimal solution even if network parameters are changing slightly over time. Two versions of the algorithm are considered: randomized and concurrent. Both versions mainain adaptability but randomized version is preferable due to better convergence rate and simpler implementation in distributed systems.
References
[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
This work is licensed under a Creative Commons Attribution 4.0 International License.
