×

A parametric maximum flow algorithm for bipartite graphs with applications. (English) Zbl 0928.90006

Summary: Suppose we are given a capacitated bipartite network \(G\) with node sets \(S\) and \(T\). In network \(G\), the arc capacities are not fixed values but are functions of a single parameter \(\lambda\), where \(\lambda\) is a continuous real variable. Our problem is to determine the minimum value of \(\lambda\) such that the maximum flow value in the corresponding network equals a given threshold. For this problem, an algorithm of time complexity \(O(nm^2\log(m/n))\) is presented, where \(n\) is the number of nodes in \(S\), \(m\) is the number of nodes in \(T\) and \(n\leq m\). Examples are then given to show how to use this parametric algorithm to solve practical problems.

MSC:

90B10 Deterministic network models in operations research
90C31 Sensitivity, stability, parametric optimization
Full Text: DOI

References:

[1] Chen, Y. L., An improved algorithm for scheduling jobs on heterogenuous processors, (National Computer Symposium, Chung-Li, Taiwan (1991)), 172-177
[2] Dinic, E. A., Algorithms for solution of a problem of maximum flow in a network with power estimation, Soviet Mathematics. Doklady, 11, 1277-1280 (1970) · Zbl 0219.90046
[3] Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM, 19, 248-264 (1972) · Zbl 0318.90024
[4] Eisner, M. J.; Severance, D. G., Mathematical techniques for efficient record segmentation in large shared databases, Journal of the ACM, 23, 619-635 (1976) · Zbl 0333.68020
[5] Gallo, G.; Grigoriadis, M. D.; Tarjan, R. E., A fast parametric flow algorithm and applications, SIAM Journal on Computing, 18, 30-55 (1989) · Zbl 0679.68080
[6] Goldberg, A. V., Finding a maximum density subgraph, (Tech. Rep. UCB/CSD 84/171 (1984), Computer Science Division, University of California: Computer Science Division, University of California Berkeley, CA)
[7] Gusfield, D.; Martel, C.; Fernandez-Baca, D., Fast algorithms for bipartite network flow, SIAM Journal on Computing, 16, 237-251 (1987) · Zbl 0617.90082
[8] Horn, W., Some simple scheduling algorithms, Naval Research Logistics Quarterly, 21, 177-185 (1974) · Zbl 0276.90024
[9] Karzanov, A. V., Determining the max flow in a network by the method of preflows, Soviet Mathematics. Doklady, 15, 434-437 (1974) · Zbl 0303.90014
[10] Malhotra, V. M.; Pramodh Kumar, M.; Maheshwari, S. N., An \(O(v^3)\) algorithm for finding maximum flows in networks, Information Processing Letters, 7, 277-278 (1978) · Zbl 0391.90041
[11] Mcnaughton, R., Scheduling with deadlines and loss functions, Management Science, 6, 1-12 (1959) · Zbl 1047.90504
[12] Picard, J. C.; Queyranne, M., A network flow solution of some nonlinear 0-1 programming problems and applications to graph theory, Networks, 12, 141-159 (1982) · Zbl 0485.90081
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.