๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A capacity scaling algorithm for M-convex submodular flow

โœ Scribed by Satoru Iwata; Satoko Moriguchi; Kazuo Murota

Publisher
Springer-Verlag
Year
2004
Tongue
English
Weight
229 KB
Volume
103
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

โœฆ Synopsis

This paper presents a faster algorithm for the M-convex submodular How problem, which is a generalization of the minimum-cost How problem with an M-convex cost function for the How-boundary, where an M-convex function is a nonlinear nonseparable cliserete convex function on integer points. The algorithm extends the capacity sealing approach lor the submodular How problem by Fleischer. Iwata and MeCormiek (2002) with the aid of a novel technique of changing the potential by solving maximum submodular How problems.

๐Ÿ“œ SIMILAR VOLUMES

A cost-scaling algorithm for 0โ€“1 submodu
A cost-scaling algorithm for 0โ€“1 submodular flows
โœ Maiko Shigeno; Satoru Iwata ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 820 KB

This paper presents a cost-scaling algorithm for minimum cost O-l 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 h

A capacity scaling algorithm for the con
A capacity scaling algorithm for the constrained maximum flow problem
โœ Ravindra K. Ahuja; James B. Orlin ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 970 KB

## Abstract The constrained maximum flow problem is to send the maximum possible flow from a source node s to a sink node t in a directed network subject to a budget constraint that the cost of flow is no more than __D__. In this paper, we consider two versions of this problem: (i) when the cost of