A cost-scaling algorithm for 0–1 submodular flows

AbstractThis paper presents a cost-scaling algorithm for minimum cost 0–1 submodular flows. The algorithm works by splitting the arc costs approximately 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 of Orlin and Ahuja's algorithm for the assignment problem