×

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

MSC:

90B10 Deterministic network models in operations research
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blyth, T. S., Module Theory, An Approach to Linear Algebra (1977), Clarendon Press: 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”, (Report No 84 340-OR (1984), Institut für Ökonometrie und Operations Research, Universität Bonn) · Zbl 0555.90080
[8] Lovász, L., Flats in matroids and geometric graphs, (Cameron, P. J., Combinatorial Surveys, Proc. 6th British Combinatorial Conference (1977), Academic Press: Academic Press New York) · 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, (Pulleyblank, W. R., Progress in Combinatorial Optimization (1984), Academic Press: Academic Press London) · Zbl 0542.90068
[12] Zimmermann, U., Linear and Combinatorial Optimization in Ordered Algebraic Structures, (Ann. Discrete Math., 10 (1981), North-Holland: North-Holland Amsterdam) · 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, (Recski, A.; Lovász, L., Matroid Theory (1982), North-Holland: North-Holland Amsterdam), 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, (Report 84-03. Report 84-03, Optimization, 17 (1986), Mathematisches Institut der Universität zu Köln), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.