×

A new scaling algorithm for the minimum cost network flow problem. (English) Zbl 0961.90011

Summary: We present a new polynomial time algorithm for solving the minimum cost network flow problem. This algorithm is based on Edmonds-Karp’s capacity scaling and Orlin’s excess scaling algorithms. Unlike these algorithms, our algorithm works directly with the given data and original network, and dynamically adjusts the scaling factor between scaling phases, so that it performs at least one flow augmentation in each phase. Our algorithm has a complexity of \(O(m(m+ n\log n)\log(B/(m + n)))\), where \(n\) is the number of nodes, \(m\) is the number of arcs, and \(B\) is the sum of the finite arc capacities and supplies in the network.

MSC:

90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K.; Goldberg, A. V.; Orlin, J. B.; Tarjan, R. E., Finding minimum cost flows by double scaing, Math. Programm., 53, 243-266 (1992) · Zbl 0761.90036
[2] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Englewood Cliffs, NJ, 1993.; R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Englewood Cliffs, NJ, 1993. · Zbl 1201.90001
[3] Ahuja, R. K.; Orlin, J. B., A capacity scaling algorithm for the constrained maximum flow problem, Networks, 25, 89-98 (1995) · Zbl 0821.90041
[4] R.G. Bland, J. Cheriyan, D.L. Jensen, L. Ladanyi, An Empirical Study of Min Cost Flow Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 12, 1993, pp. 119-156.; R.G. Bland, J. Cheriyan, D.L. Jensen, L. Ladanyi, An Empirical Study of Min Cost Flow Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 12, 1993, pp. 119-156. · Zbl 0787.90019
[5] Bland, R. G.; Jensen, D. L., On the computational behavior of a polynomial-time network flow algorithm, Math. Programm., 54, 1-39 (1992) · Zbl 0767.90013
[6] Dijkstra, E., A note on two problems in connexion with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[7] Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19, 248-264 (1972) · Zbl 0318.90024
[8] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM, 34, 596-615 (1987) · Zbl 1412.68048
[9] S. Fujishige, K. Iwano, J. Nakano, S. Tezuka, A Speculative Contraction Method for Minimum Cost Flows: Toward a Practical Algorithm, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 12, 1993, pp. 219-245.; S. Fujishige, K. Iwano, J. Nakano, S. Tezuka, A Speculative Contraction Method for Minimum Cost Flows: Toward a Practical Algorithm, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 12, 1993, pp. 219-245. · Zbl 0787.90020
[10] Gabow, H. N., Scaling algorithms for network problems, J. Comput. System Sci., 31, 148-168 (1985) · Zbl 0596.90095
[11] A.V. Goldberg, M. Kharitonov, On Implementing Scaling Push-Relabel Algorithms for the Minimum-Cost Flow Problem, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 12, 1993, pp. 157-198.; A.V. Goldberg, M. Kharitonov, On Implementing Scaling Push-Relabel Algorithms for the Minimum-Cost Flow Problem, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 12, 1993, pp. 157-198. · Zbl 0787.90021
[12] Goldberg, A. V.; Tarjan, R. E., Solving minimum cost flow problems by successive approximation, Math. Oper. Res., 15, 430-466 (1990) · Zbl 0727.90024
[13] Goldfarb, D.; Jin, Z., A faster combinatorial algorithm for the generalized circulation problem, Math. Oper. Res., 21, 529-539 (1996) · Zbl 0873.90100
[14] D. Goldfarb, Z. Jin, Strongly polynomial excess scaling and dual simplex algorithms for the minimum cost network flow problem, Technical Report, IEOR Department, Columbia University, New York, NY, 1996.; D. Goldfarb, Z. Jin, Strongly polynomial excess scaling and dual simplex algorithms for the minimum cost network flow problem, Technical Report, IEOR Department, Columbia University, New York, NY, 1996.
[15] Goldfarb, D.; Jin, Z.; Orlin, J. B., Polynomial-time highest-gain augmenting path algorithms for the generalized circulation problem, Math. Oper. Res., 22, 793-802 (1997) · Zbl 0892.90064
[16] Ikura, Y.; Nemhauser, G. L., Computational experience with a polynomial-time dual simplex algorithm for the transportation problem, Discrete Appl. Math., 13, 239-248 (1986) · Zbl 0587.90068
[17] Orlin, J. B., A faster strongly polynomial minimum cost flow algorithm, Oper. Res., 41, 338-350 (1993) · Zbl 0781.90036
[18] Orlin, J. B.; Plotkin, S. A.; Tardos, E., Polynomial dual network simplex algorithms, Math. Programm., 60, 255-276 (1993) · Zbl 0784.90097
[19] H. Rock, Scaling techniques for minimal cost network flows, in: V. Page (Ed.), Discrete Structures and Algorithms, Carl Hansen, Munich, 1980, pp. 181-191.; H. Rock, Scaling techniques for minimal cost network flows, in: V. Page (Ed.), Discrete Structures and Algorithms, Carl Hansen, Munich, 1980, pp. 181-191. · Zbl 0458.90021
[20] Tardos, E., A strongly polynomial minimum cost circulation algorithm, Combinatorica, 5, 247-255 (1985) · Zbl 0596.90030
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.