A faster capacity scaling algorithm for minimum cost submodular flow

Lisa Fleischer (), Satoru Iwata () and Thomas McCORMICK ()
Additional contact information
Lisa Fleischer: Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027, USA
Satoru Iwata: Division of Systems Science, Graduate School of Engineering Sciences, Osaka University, Toyonaka, Osaka 560- 8531, Japan
Thomas McCORMICK: Faculty of Commerce and Business Administration, University of British Columbia, Vancouver, BC V6T 1Z2 Canada

No 1999047, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We describe an O(n[exp.4]h min{log U, n[exp.2] log n}) capacity scaling algorithm for the minimum cost submodular flow problem.Our algorithm modifies and extends the Edmonds-Karp capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails scaling a relaxation parameter [delta]. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity [delta] in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polytope of a relaxed submodular function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along min cost paths of residual capacity at least [delta]. The shortest augmenting path subroutine we use is a variant of Dijkstra's algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use max mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow.

Keywords: submodular flow; shortest paths; strongly polynomial time algorithm (search for similar items in EconPapers)
Date: 1999-07-01
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1999.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1999047

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().