Minimal cost flows in regular matroids

In this paper flows in regular matroids M are considered and three algorithms are described for determining maximal matroid flows with minimal costs. The first algorithms starts with an arbitrary maximal matroid flow and reduces its costs by finding negative circuits in M. The second builds up a min cost matroid flow by starting with the zero flow and performing augmentations along shortest augmenting circuits. The last algorithm works in regular matroids with special structures. By a sequence of admissible transformations an optimal matroid flow can be found. This transformation method can be viewed as a generalization of the Hungarian Method for solving linear assignment problems. The arguments used in the paper are of pure combinatorial kind and don’t make any use of the representation of the regular matroid M by a totally unimodular matrix.