Duality for balanced submodular flows
type: Item
instance of: scholarly article
title: Duality for balanced submodular flows
zbMATH Open document ID: 0626.90023
DOI: 10.1016/0166-218X(86)90053-3
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
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.
reviewed by: Horst W. Hamacher
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4018735
zbMATH Keywords: duality
zbMATH Keywords: balanced flow problems
zbMATH Keywords: balanced submodular flow
zbMATH Keywords: polynomial complexity bounds
author: Uwe T. Zimmermann
MaRDI profile type: Publication
cites work: Q4123451
cites work: Q4149476
cites work: An Algorithm for Submodular Functions on Graphs
cites work: Finding feasible vectors of Edmonds-Giles polyhedra
cites work: Structures of polyhedra determined by submodular functions on crossing families
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Corrigendum to our paper ''The ellipsoid method and its consequences in combinatorial optimization''
cites work: Q4133994
cites work: Combinatorial Optimization with Rational Objective Functions
cites work: Q3330974
cites work: Linear and combinatorial optimization in ordered algebraic structures
cites work: Minimization on submodular flows
cites work: Q3725833
cites work: Linear and combinatorial sharing problems
cites work: Sharing problems
full work available at URL: 0166-218x(86)90053-3
OpenAlex ID: W2042718895
description: scientific article; zbMATH DE number 4018735