Fecha: |
1997 |
Resumen: |
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. . |
Derechos: |
Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.  |
Lengua: |
Anglès |
Documento: |
Article ; recerca ; Versió publicada |
Materia: |
Submodular flow ;
Polynomial algorithm ;
Convex optimization |
Publicado en: |
Mathematical Programming, vol. 76 n. 2 (1997) p. 299-308, ISSN 0025-5610 |