A Colored Gauss-Seidel Approach for the Distributed Network Flow Problem

A distributed solution for the minimum cost network flow problem is here proposed. The method uses a block version of the Gauss-Seidel algorithm in order to iteratively solve the dual problem whose structure is such that the Hessian matrix coincides with the Laplacian matrix of the corresponding graph. Thus, the updating rule turns out to be fully distributed. In order to increase the parallelism degree, a graph coloring scheme allows the clustering of nodes that reduces the sequentiality of the Gauss-Seidel technique. Numerical experiments show the effectiveness of the approach compared with methods recently presented in the literature.