A Primal-Dual Algorithm for Submodular Flows

DOI10.1287/MOOR.10.2.251MaRDI QIDQ3680637zbMATH OpenOpenAlexFDO

Authors William H. Cunningham, András Frank

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 graphsellipsoid methodoptimal submodular floworacle methodspolynomial-time solution algorithmprimal-dual algorithm

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3885621
• A dual algorithm for submodular flow problems
• A fast cost scaling algorithm for submodular flow
• Improved algorithms for submodular function minimization and submodular flow
• scientific article; zbMATH DE number 1263281

Cited in

(37)

• Testing membership in matroid polyhedra
• A strongly polynomial minimum cost circulation algorithm
• An out-of-kilter method for submodular flows
• An application of simultaneous diophantine approximation in combinatorial optimization
• Generalized polymatroids and submodular flows
• Directed submodularity, ditroids and directed submodular flows
• An application of submodular flows
• A dual algorithm for submodular flow problems
• Negative circuits for flows and submodular flows
• On the complexity of the dual method for maximum balanced flows
• A capacity scaling algorithm for convex cost submodular flows
• Optimum partitioning into intersections of ring families
• Application of M-convex submodular flow problem to mathematical economics
• Coordinatewise domain scaling algorithm for M-convex function minimization
• A capacity scaling algorithm for M-convex submodular flow
• Polyhedral structure of submodular and posi-modular systems
• Fast cycle canceling algorithms for minimum cost submodular flow
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• Simple push-relabel algorithms for matroids and submodular flows
• Fair integral submodular flows
• The edge-orientation problem and some of its variants on weighted graphs
• A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows
• A fast cost scaling algorithm for submodular flow
• A primal-dual algorithm for weighted abstract cut packing
• Algorithms for submodular totally dual integral problems
• A submodular network simplex method
• scientific article; zbMATH DE number 3885621 (Why is no real title available?)
• scientific article; zbMATH DE number 3934774 (Why is no real title available?)
• scientific article; zbMATH DE number 3956777 (Why is no real title available?)
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• A PRIMAL ALGORITHM FOR THE SUBMODULAR FLOW PROBLEM WITH MINIMUM-MEAN CYCLE SELECTION
• scientific article; zbMATH DE number 1263281 (Why is no real title available?)
• scientific article; zbMATH DE number 1303553 (Why is no real title available?)
• Duality for balanced submodular flows
• A Unified Framework for Pricing in Nonconvex Resource Allocation Games
• Submodular hypergraph partitioning: metric relaxations and fast algorithms via an improved cut-matching game
• Finding feasible vectors of Edmonds-Giles polyhedra

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

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