A capacity scaling algorithm for convex cost submodular flows

DOI10.1007/BF02614442zbMath0882.90037OpenAlexW3138620896MaRDI QIDQ1363412

Satoru Iwata

Publication date: 7 August 1997

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02614442

zbMATH Keywords

minimum cost integral submodular flowscaling scheme for submodular functionsseparable convex cost functions

Mathematics Subject Classification ID

Convex programming (90C25) Deterministic network models in operations research (90B10)

Related Items (10)

A fast cost scaling algorithm for submodular flow ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ A push-relabel framework for submodular function minimization and applications to parametric optimization ⋮ Minimizing a sum of submodular functions ⋮ A capacity scaling algorithm for M-convex submodular flow ⋮ Submodular function minimization ⋮ A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives ⋮ Extension of M-convexity and L-convexity to polyhedral convex functions ⋮ Minimizing a submodular function arising from a concave function ⋮ A fully combinatorial algorithm for submodular function minimization.

Cites Work

• Unnamed Item
• Unnamed Item
• Finding feasible vectors of Edmonds-Giles polyhedra
• Generalized polymatroids and submodular flows
• Submodular functions and optimization
• Structures of polyhedra determined by submodular functions on crossing families
• A Primal-Dual Algorithm for Submodular Flows
• Solving integer minimum cost flows with separable convex cost objective polynomially
• Layered Augmenting Path Algorithms
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Convex separable optimization is not much harder than linear optimization

This page was built for publication: A capacity scaling algorithm for convex cost submodular flows