A capacity scaling algorithm for convex cost submodular flows

DOI10.1007/BF02614442MaRDI QIDQ1363412zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Integer Programming and Combinatorial Optimization
• A capacity scaling algorithm for M-convex submodular flow
• A faster capacity scaling algorithm for minimum cost submodular flow
• A fast cost scaling algorithm for submodular flow
• A cost-scaling algorithm for \(0-1\) submodular flows

Cites work

• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• A Primal-Dual Algorithm for Submodular Flows
• Convex separable optimization is not much harder than linear optimization
• Finding feasible vectors of Edmonds-Giles polyhedra
• Generalized polymatroids and submodular flows
• Layered Augmenting Path Algorithms
• Network flows. Theory, algorithms, and applications.
• Solving integer minimum cost flows with separable convex cost objective polynomially
• Structures of polyhedra determined by submodular functions on crossing families
• Submodular functions and optimization
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(19)

• Extension of M-convexity and L-convexity to polyhedral convex functions
• Submodular function minimization
• Capacitated Confluent Flows: Complexity and Algorithms
• A capacity scaling algorithm for the constrained maximum flow problem
• A fully combinatorial algorithm for submodular function minimization.
• Minimizing a sum of submodular functions
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• A fast cost scaling algorithm for submodular flow
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• Minimizing a submodular function arising from a concave function
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A capacity scaling algorithm for M-convex submodular flow
• Separable convexification and DCA techniques for capacity and flow assignment problems.
• A faster capacity scaling algorithm for minimum cost submodular flow
• Capacity scaling algorithm for scalable M-convex submodular flow problems
• Integer Programming and Combinatorial Optimization
• Data Center Scheduling, Generalized Flows, and Submodularity
• Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization
• A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363412)