A Primal-Dual Algorithm for Submodular Flows

DOI10.1287/MOOR.10.2.251zbMath0565.90079OpenAlexW2056006039MaRDI QIDQ3680637

András Frank, William H. Cunningham

Publication date: 1985

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.10.2.251

zbMATH Keywords

directed graphsprimal-dual algorithmellipsoid methodoracle methodsoptimal submodular flowpolynomial-time solution algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Deterministic network models in operations research (90B10)

Related Items (21)

A strongly polynomial minimum cost circulation algorithm ⋮ A fast cost scaling algorithm for submodular flow ⋮ An out-of-kilter method for submodular flows ⋮ An application of simultaneous diophantine approximation in combinatorial optimization ⋮ A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm ⋮ A capacity scaling algorithm for convex cost submodular flows ⋮ Optimum partitioning into intersections of ring families ⋮ Fair integral submodular flows ⋮ Generalized polymatroids and submodular flows ⋮ Directed submodularity, ditroids and directed submodular flows ⋮ An application of submodular flows ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ A Unified Framework for Pricing in Nonconvex Resource Allocation Games ⋮ A dual algorithm for submodular flow problems ⋮ Coordinatewise domain scaling algorithm for M-convex function minimization ⋮ A capacity scaling algorithm for M-convex submodular flow ⋮ A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows ⋮ The edge-orientation problem and some of its variants on weighted graphs ⋮ Polyhedral structure of submodular and posi-modular systems ⋮ Testing membership in matroid polyhedra ⋮ Finding feasible vectors of Edmonds-Giles polyhedra

This page was built for publication: A Primal-Dual Algorithm for Submodular Flows