Duality for balanced submodular flows

DOI10.1016/0166-218X(86)90053-3MaRDI QIDQ581206zbMATH OpenOpenAlexFDO

Authors Uwe T. Zimmermann

Publication date 1986

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(86)90053-3

zbMATH Keywords

balanced flow problemsbalanced submodular flowdualitypolynomial complexity bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Review text

A (single source-single sink) flow is called balanced if for all arcs e the flow value x(e) does not exceed a given proportion of the total flow from source to sink. After discussing a basic dual approach which works in the general context of totally ordered sets, the author shows that his approach can be used to solve parametric problems which are equivalent to balanced flow problems. The discussion is further generalized by considering general balanced submodular flow problems. In both cases genuinely polynomial complexity bounds are derived for the resulting algorithms.

Recommendations

• On the complexity of the dual method for maximum balanced flows
• Balancing Applied to Maximum Network Flow Problems
• A dual algorithm for submodular flow problems
• A NETWORK SIMPLEX METHOD FOR THE MAXIMUM BALANCED FLOW PROBLEM
• A Primal-Dual Algorithm for Submodular Flows

Cites work

• An Algorithm for Submodular Functions on Graphs
• Combinatorial Optimization with Rational Objective Functions
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• Finding feasible vectors of Edmonds-Giles polyhedra
• scientific article; zbMATH DE number 3862931 (Why is no real title available?)
• scientific article; zbMATH DE number 3956777 (Why is no real title available?)
• scientific article; zbMATH DE number 3549138 (Why is no real title available?)
• scientific article; zbMATH DE number 3561367 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• Linear and combinatorial optimization in ordered algebraic structures
• Linear and combinatorial sharing problems
• Minimization on submodular flows
• Sharing problems
• Structures of polyhedra determined by submodular functions on crossing families
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(7)

• On the equivalence of the maximum balanced flow problem and the weighted minimax flow problem
• On the complexity of the dual method for maximum balanced flows
• Towards equitable distribution via proportional equity constraints
• A note on \(K\) best network flows
• Duality in balance optimization subset selection
• A submodular optimization problem with side constraints
• A strongly polynomial time algorithm for a constrained submodular optimization problem

This page was built for publication: Duality for balanced submodular flows

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