A COST-SCALING ALGORITHM FOR 0-1-SUBMODULAR FLOWS

This paper presents a cost-scaling algorithm for minimum cost 0-1 subm odular flows. The algorithm works by splitting the are costs approxima tely and maintaining an optimal submodular pseudoflow with respect to the split costs obtained by a greedy algorithm. Each scaling phase of the algorithm is a hybrid version of an auction-like method with cost- splitting and a successive-shortest-path method, as a generalization o f Orlin and Ahuja's algorithm for the assignment problem.