A dual algorithm for submodular flow problems

DOI10.1016/0167-6377(91)90027-MzbMath0754.90023MaRDI QIDQ1183393

Nam-kee Chung, Dong-wan Tcha

Publication date: 28 June 1992

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

dual algorithmsteepest ascent methodsubmodular flow problembest improving set

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (4)

A fast cost scaling algorithm for submodular flow ⋮ Dijkstra's algorithm and L-concave function maximization ⋮ Algorithms for the minimum cost circulation problem based on maximizing the mean improvement ⋮ Exact bounds for steepest descent algorithms of $L$-convex function minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding feasible vectors of Edmonds-Giles polyhedra
• An out-of-kilter method for submodular flows
• Generalized polymatroids and submodular flows
• Minimization on submodular flows
• The ellipsoid method and its consequences in combinatorial optimization
• A submodular network simplex method
• A Primal-Dual Algorithm for Submodular Flows
• A unified framework for primal-dual methods in minimum cost network flow problems
• Submodular systems and related topics
• Dual Algorithms for Pure Network Problems
• The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
• An Algorithm for Submodular Functions on Graphs

This page was built for publication: A dual algorithm for submodular flow problems