zbMATH — the first resource for mathematics

Duality for balanced submodular flows. (English) Zbl 0626.90023
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.
Reviewer: H.Hamacher

90B10 Deterministic network models in operations research
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Blyth, T.S., Module theory, an approach to linear algebra, (1977), Clarendon Press Oxford · Zbl 0353.15004
[2] Edmonds, J.; Giles, R., A MIN-MAX relation for submodular functions on graphs, Ann. discrete math., 1, 185-204, (1977)
[3] Frank, A., An algorithm for submodular functions on graphs, Ann. discrete math., 16, 97-120, (1982) · Zbl 0504.05059
[4] Frank, A., Finding feasible vectors of edmonds-giles polyhedra, J. combin. theory (B), 36, 221-239, (1984) · Zbl 0544.05016
[5] Fujishige, S., Structures of polyhedra determined by submodular functions on crossing families, Math. programming, 29, 125-141, (1984) · Zbl 0545.90097
[6] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequence in combinatorial optimazation, Combinatorica, 1, 169-197, (1981) · Zbl 0492.90056
[7] Grötschel, M.; Lovász, L.; Schrijver, A., Corrigendum to our paper “the ellipsoid method and its consequences in combinatorial optimization”, () · Zbl 0555.90080
[8] Lovász, L., Flats in matroids and geometric graphs, () · Zbl 0361.05027
[9] Meggido, N., Combinatorial optimization with rational objective functions, Math. oper. res., 4, 414-429, (1979)
[10] Minoux, M., Flots équilibr’es et flots avec sécurité, Bull. direction etudes recherches Sér. C. math. informat., 5-16, (1976)
[11] Schrijver, A., Total dual integrality from directed graphs, crossing families, and sub- and super-modular functions, () · Zbl 0542.90068
[12] Zimmermann, U., Linear and combinatorial optimization in ordered algebraic structures, () · Zbl 0466.90045
[13] Zimmermann, U., Minimization on submodular flows, Discrete appl. math., 4, 303-323, (1982) · Zbl 0491.90041
[14] Zimmermann, U., Augmenting circuit methods for submodular flow problems, (), 401-439 · Zbl 0594.90024
[15] Zimmermann, U., Linear and combinatorial sharing problems, Discrete appl. matl., 15, 85-104, (1986) · Zbl 0601.90120
[16] Zimmermann, U., Sharing problems, (), 31-47 · Zbl 0591.90074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.