| Article ID: | iaor1998383 |
| Country: | Netherlands |
| Volume: | 76 |
| Issue: | 2 |
| Start Page Number: | 299 |
| End Page Number: | 308 |
| Publication Date: | Feb 1997 |
| Journal: | Mathematical Programming |
| Authors: | Iwata Satoru |
| Keywords: | networks: flow |
This paper presents a scaling scheme for submodular functions. A small but strictly submodular function is added before scaling so that the resulting functions should be submodular. This scaling scheme leads to a weakly polynomial algorithm to solve minimum cost integral submodular flow problems with separable convex cost functions, provided that an oracle for exchange capacities is available.