×

A note on the parametric maximum flow problem and some related reoptimization issues. (English) Zbl 1144.90504

Summary: In this paper, we will extend the results about the parametric maximum flow problem to networks in which the parametrization of the arc capacities can involve both the source and the sink, as in G. Gallo, M. D. Grigoriadis and R. E. Tarjan [SIAM J. Comput. 18, No.1, 30–55 (1989; Zbl 0679.68080)], and also an additional node. We will show that the minimum cuts of the investigated networks satisfy a relaxed form of the generalized nesting property [T. Arai et al., Discrete Appl. Math. 41, No. 1, 69–74 (1993; Zbl 0780.90029)]. A consequence is that the corresponding parametric maximum flow value function has at most \(n - 1\) breakpoints. All the minimum cut capacities can therefore be computed by \(O(1)\) maximum flow computations. We will show then that, given \(O(n)\) increasing values of the parameter, it is possible to compute the corresponding maximum flows by \(O(1)\) maximum flow computations, by suitably extending Goldberg and Tarjan’s maximum flow algorithm.

MSC:

90C35 Programming involving graphs or networks
90C31 Sensitivity, stability, parametric optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R.K., T.L. Magnanti, and J.B. Orlin. (1993). Network Flows: Theory, Algorithms and Applications. Englewood Cliffs, NJ: Prentice Hall. · Zbl 1201.90001
[2] Arai, T., S. Ueno, and Y. Kajitani. (1993). ”Generalization of a Theorem on the Parametric Maximum Flow Problem.” Discrete Applied Mathematics, 41, 69–74. · Zbl 0780.90029 · doi:10.1016/0166-218X(93)90245-J
[3] Brumelle, S., D. Granot, and L. Liu. (2002). ”Ordered Optimal Solutions and Parametric Minimum Cut Problems.” Working paper. · Zbl 1077.90073
[4] Carstensen, P.J. (1983). ”Complexity of Some Parametric Integer and Network Programming Problems.” Mathematical Programming, 26, 64–75. · Zbl 0585.90065 · doi:10.1007/BF02591893
[5] Ford Jr., L.R. and D.R. Fulkerson. (1962). Flows in Networks. Princeton, NJ: Princeton University Press. · Zbl 0106.34802
[6] Gallo, G., M.D. Grigoriadis, and R.E. Tarjan. (1989). ”A Fast Parametric Maximum Flow Algorithm and Applications.” SIAM J. Comp., 18(1), 30–55. · Zbl 0679.68080 · doi:10.1137/0218003
[7] Goldberg, A.V. and R.E. Tarjan. (1986). ”A New Approach to the Maximum Flow Problem.” Proc. 18th Annual ACM Symposium on Theory of Computing, 136–146.
[8] Goldberg, A.V. and R.E. Tarjan. (1988). ”A New Approach to the Maximum Flow Problem.” JACM, 35(4), 921–940. · Zbl 0661.90031 · doi:10.1145/48014.61051
[9] Gusfield, D. and C. Martel. (1992). ”A Fast Algorithm for the Generalized Parametric Minimum Cut Problem and Applications.” Algorithmica, 7, 499–519. · Zbl 0763.90081 · doi:10.1007/BF01758775
[10] McCormick, S.T. (1999). ”Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow.” Operations Research, 47(5), 744–756. · Zbl 0982.90023 · doi:10.1287/opre.47.5.744
[11] Sleator, D.D. and R.E. Tarjan. (1983). ”A Data Structure for Dynamic Trees.” J. Comput. System Sci., 24, 362–391. · Zbl 0509.68058 · doi:10.1016/0022-0000(83)90006-5
[12] Sleator, D.D. and R.E. Tarjan. (1985). ”Self-Adjusting Binary Search Trees.” JACM, 32, 652–686. · Zbl 0631.68060 · doi:10.1145/3828.3835
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.