×

Finding minimum-cost flows by double scaling. (English) Zbl 0761.90036

Summary: Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. We combine several of these techniques to yield an algorithm running in \(O(nm(\log\log U)\log(nC))\) time on networks with \(n\) vertices, \(m\) edges, maximum arc capacity \(U\), and maximum arc cost magnitude \(C\). The major techniques used are the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja and Orlin, the cost-scaling approach of Goldberg and Tarjan, and the dynamic tree data structure of Sleator and Tarjan. For nonsparse graphs with large maximum arc capacity, we obtain a similar but slightly better bound. We also obtain a slightly better bound for the (noncapacitated) transportation problem. In addition, we discuss a capacity-bounding approach to the minimum-cost flow problem.

MSC:

90B10 Deterministic network models in operations research
90C60 Abstract computational complexity for mathematical programming problems
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] R.K. Ahuja and J.B. Orlin, ”A fast and simple algorithm for the maximum flow problem,”Operations Research 37 (1989) 939–954. · Zbl 0691.90024
[2] R.K. Ahuja, J.B. Orlin and R.E. Tarjan, ”Improved time bounds for the maximum flow problem,”SIAM Journal on Computing 18 (1989) 939–954. · Zbl 0675.90029
[3] D.P. Bertsekas, ”A distributed algorithm for the assignment problem,” unpublished working paper, Laboratory for Information and Decision Science, M.I.T. (Cambridge, MA, 1979).
[4] D.P. Bertsekas, ”Distributed asynchronous relaxation methods for linear network flow problems,” Technical Report LIDS-P-1606, Laboratory for Information and Decision Sciences, M.I.T. (Cambridge, MA, 1986).
[5] E.A. Dinic, ”Algorithm for solution of a problem of maximum flow in networks with power estimation,”Soviet Mathematics Doklady 11 (1970) 1277–1280. · Zbl 0219.90046
[6] J. Edmonds and R.M. Karp, ”Theoretical improvements in algorithmic efficiency for network flow problems,”Journal of the Association on Computing Machinery 19 (1972) 248–264. · Zbl 0318.90024
[7] H.N. Gabow, ”Scaling algorithms for network problems,”Journal of Computer and System Sciences 31 (1985) 148–168. · Zbl 0596.90095
[8] H.N. Gabow and R.E. Tarjan, ”Faster scaling algorithms for networks problems,”SIAM Journal on Computing 18 (1989) 1013–1036. · Zbl 0679.68079
[9] A.V. Goldberg, ”Efficient graph algorithms for sequential and parallel computers,” Ph.D. Thesis, M.I.T. (Cambridge, MA, 1987).
[10] A.V. Goldberg and R.E. Tarjan, ”A new approach to the maximum flow problem,”Journal of the Association for Computing Machinery 35 (1988) 921–940. · Zbl 0661.90031
[11] A.V. Goldberg and R.E. Tarjan, ”Finding minimum-cost circulations by successive approximation,”Mathematics of Operations Research 15 (1990) 430–466. · Zbl 0727.90024
[12] A.V. Goldberg and R.E. Tarjan, ”Finding minimum-cost circulations by canceling negative cycles,”Journal of the Association for Computing Machinery 36 (1989) 873–886; alsoProceedings of the Twentieth Annual ACM Symposium on Theory of Computing (1988), 388–397. · Zbl 0697.68063
[13] E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Reinhart and Winston, New York, 1976). · Zbl 0413.90040
[14] R. Melhorn,Data Structures and Algorithms, Vol. 1: Sorting and Searching (Springer, Berlin, 1984).
[15] J.B. Orlin, ”On the simplex algorithm for networks and generalized networks,”Mathematical Programming 23 (1985) 166–178. · Zbl 0592.90031
[16] J. Orlin, ”A faster strongly polynomial minimum cost flow algorithm,”Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (1988) 377–387.
[17] C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, N.J, 1982). · Zbl 0503.90060
[18] D.D. Sleator and R.E. Tarjan, ”A data structure for dynamic trees,”Journal of Computer and System Sciences 26 (1983) 362–391. · Zbl 0509.68058
[19] D.D. Sleator and R.E. Tarjan, ”Self-adjusting binary search trees,”Journal of the Association for Computing Machinery 32 (1985) 652–686. · Zbl 0631.68060
[20] E. Tardos, ”A strongly polynomial minimum cost circulation algorithm,”Combinatorica 5 (1985) 247–255. · Zbl 0596.90030
[21] R.E. Tarjan,Data Structures and Network Algorithms (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983). · Zbl 0584.68077
[22] R.E. Tarjan and C.J. van Wyk, ”An O(n log logn)-time algorithm for triangulating a simple polygon,”SIAM Journal on Computing 17 (1988) 143–178. · Zbl 0637.68044
[23] H.M. Wagner, ”On a class of capacitated transportation problems,”Management Science 5 (1959) 304–318. · Zbl 0995.90513
[24] N. Zadeh, ”A bad network flow problem for the simplex method and other minimum cost flow algorithms,”Mathematical Programming 5 (1973) 255–266. · Zbl 0287.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. 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.