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.