A Cost-scaling Algorithm for 0-1 Submodular Flows

A Cost-scaling Algorithm for 0-1 Submodular Flows,10.1016/S0166-218X(96)00011-X,Discrete Applied Mathematics,Maiko Shigeno,Satoru Iwata

A Cost-scaling Algorithm for 0-1 Submodular Flows   (Citations: 1)
BibTex | RIS | RefWorks Download
This 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.
Journal: Discrete Applied Mathematics - DAM , vol. 73, no. 3, pp. 261-273, 1997
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: