A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow.

We describe an @( n^4 h min{log U, n^2logn}) 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.

MoreLess

Year of publication:	1999
Authors:	Fleischer, L. ; Iwata, S. ; MaCormick, S.T.
Institutions:	Center for Operations Research and Econometrics (CORE), École des Sciences Économiques de Louvain
Subject:	MATHEMATICAL ANALYSIS

More details

Series:	Papers.
Type of publication:	Book / Working Paper
Notes:	18 pages
Classification:	C00 - Mathematical and Quantitative Methods. General ; C60 - Mathematical Methods and Programming. General
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005634186