Parallel primal-dual methods for the minimum cost flow problem (Q1315451)

The subject of this paper is an asynchronous implementation of the classical path-augmentation algorithm for minimum-cost capacitated flow problem. The technique allows multiple parallel flow augmentation computations with potentially outdated data and the authors show that the resulting algorithm converges in a finite number of iterations subject to mild conditions. Computation times are reported for two NETGEN problems indicating reductions of the computation times of up to 20\% with respect to a synchronous parallel implementation of the algorithm.