Andrew V. Goldberg
Satish Rao
Abstract
We introduce a new approach to the maximum flow problem. This approach is based on assigning arc lengths based on the residual flow value and the residual arc capacities. Our approach leads to an O(min(n2/3, m1/2)m log(n2/m) log U) time bound for a network with n vertices, m arcs, and integral arc capacities in the range [1, …, U]. This is a fundamental improvement over the previous time bounds. We also improve bounds for the Gomory-Hu tree problem, the parametric flow problem, and the approximate s-t cut problem.
- ADEL'SON-VEL'SKI, G. M., DINIC, E. A., AND KARZANOV, A. V. 1975. Flow Algorithms. Nauka, Moscow, CIS (in Russian).Google Scholar
- AHUJA, R. K., AND ORLIN, J.B. 1989. A fast and simple algorithm for the maximum flow problem. Oper. Res. 37, 748-759.Google Scholar
- AHUJA, R. K., ORLIN, J. B., AND TARJAN, R.E. 1989. Improved time bounds for the maximum flow problem. SIAM J. Comput. 18, 939-954. Google Scholar
- ALON, N. 1990. Generating pseudo-random permutations and maximum flow algorithms. Inf. Proc. Lett. 35, 201-204. Google Scholar
- ANDERSON, R. J., AND SETUBAL, J. C. 1993. Goldberg's algorithm for the maximum flow in perspective: A computational study. In Network Flows and Matching: First DIMACS Implementation Challenge, D. S. Johnson and C. C. McGeoch, eds. American Mathematics Society, Providence, R.I., pp. 1-18.Google Scholar
- BENCZIJR, A. A., AND KARGER, D.R. 1996. Approximating s-t minimum cuts in O(n2) time. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (Philadelphia, Pa., May 22-24). ACM, New York. pp. 47-55. Google Scholar
- CHERIYAN, J., HAGERUP, f., AND MEHLHORN, K. 1996. O(n3)-time maximum-flow algorithm. SIAM J. Comput. 45, 1144-1170. Google Scholar
- CHERKASSKY, R.V. 1977. Algorithm for construction of maximal flows in networks with complex-ity of O(V2 X/-E) operations. Math. Meth. Sol. Economic. Prob. 7, 112-125 (in Russian).Google Scholar
- CHERKASSKY, B. V., AND GOLDBERG, A.V. 1995. On implementing push-relabel method for the maximum flow problem. In Proceedings of the 4th International Programming and Combinatorial Optimization Conference. Lecture Notes in Computer Science. Springer-Verlag, New York, pp. 157-171. Google Scholar
- DANTZIG, G.B. 1951. Application of the simplex method to a transportation problem. In Activity Analysis and Production and Allocation. Wiley, New York, pp. 359-373.Google Scholar
- DERIGS, U., AND MEIER, W. 1989. Implementing Goldberg's Max-Flow algorithm--A computational investigation. ZOR-Meth. Mod. Oper. Res. 33, 383-403.Google Scholar
- DIAL, R.B. 1969. Algorithm 360: Shortest-path forest with topological ordering. Commun. ACM 12, 11 (Nov.), 631-633. Google Scholar
- DINIC, E.A. 1970. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Dokl. 11, 1277-1280.Google Scholar
- DINIC, E. A. 1973. Metod porazryadnogo sokrashcheniya nevyazok i transportnye zadachi. In Issledovaniya po Diskretnoi Matematike. Nauka, Moskva, CIS (in Russian; Title translation: Excess Scaling and Transportation Problems), pp. 46-57.Google Scholar
- EDMONDS, J., AND KARP, R. M. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 2 (Apr.), 248-264. Google Scholar
- EVEN, S., AND TARJAN, R.E. 1975. Network flow and testing graph connectivity. SIAM J. Comput. 4, 507-518.Google Scholar
- FORD, JR., L. R., AND FULKERSON, D.R. 1956. Maximal flow through a network. Canad. J. Math. 8, 399 - 404.Google Scholar
- FORD, JR., L. R., AND FULKERSON, D. R. 1962. Flows in Networks. Princeton Univ. Press, Princeton, N.J.Google Scholar
- GABOW, H.N. 1985. Scaling algorithms for network problems. J. Comput. Syst. Sci. 31, 148-168. Google Scholar
- GALIL, Z., AND NAAMAD, A. 1980. An O(EV log2V) algorithm for the maximal flow problem. J. Comput. Syst. Sci. 21, 203-217.Google Scholar
- GALLO, G., GRIGORIADIS, M. D., AND TARJAN, R. E. 1989. A fast parametric maximum flow algorithm. SIAM J. Comput. 18, 30-55. Google Scholar
- GOLDBERG, A.V. 1985. A new Max-Flow algorithm. Tech Rep. MIT/LCS/TM-291. Laboratory for Computer Science, MIT, Cambridge, Mass.Google Scholar
- GOLDBERG, A.V. 1987. Efficient graph algorithms for sequential and parallel computers. Ph.D. dissertation. MIT, Cambridge, Mass. (Also available as Tech Rep. TR-374, Laboratory for Computer Science, MIT, Cambridge, Mass., 1987.) Google Scholar
- GOLDBERG, A. V., AND RAO, S. 1997. Flows in undirected unit capacity networks. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 32-35. Google Scholar
- GOLDBERG, A. V., AND TARJAN, R.E. 1988. A new approach to the maximum-flow problem. J. ACM 35, 4 (Oct.), 921-940. Google Scholar
- GOLDBERG, A. V., AND TARJAN, R. E. 1990. Finding minimum-cost circulations by successive approximation. Math. Oper. Res. 15, 430-466. Google Scholar
- GOMORY, R. E., AND HU, T.C. 1961. Multi-terminal network flows. J. SIAM 9, 551-570.Google Scholar
- GUSFmLD, D. 1990. Very simple methods for all pairs networks flow analysis. SIAM J. Comput. 19, 143-155. Google Scholar
- KARGER, D.R. 1997. Using random sampling to find maximum flows in uncapacitated undirected graphs. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 240-249. Google Scholar
- KARZANOV, A. V. 1973. O nakhozhdenii maksimal'nogo potoka v setyakh spetsial'nogo vida i nekotorykh prilozheniyakh. In Matematicheskie Voprosy Upravleniya Proizvodstvom, vol. 5. Moscow State University Press, Moscow, CIS (in Russian; title translation: On finding maximum flows in networks with special structure and some applications).Google Scholar
- KARZANOV, A.V. 1974. Determining the maximal flow in a network by the method of preflows. Soviet Math. Dokl. 15, 434-437.Google Scholar
- KING, V., RAO, S., AND TARJAN, R. 1992. A faster deterministic maximum flow algorithm. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, Fla., Jan. 27-29). ACM, New York, pp. 157-164. Google Scholar
- KING, V., RAO, S., AND TARJAN, R. 1994. A faster deterministic maximum flow algorithm. J. Algorithms 17, 447-474. Google Scholar
- KNUTH, D.E. 1974. Wheels within wheels. J. Combinat. Theory 16, 42-46.Google Scholar
- MIDDLETON, A. A. 1995. Numerical results for the ground-state interface in random medium. Phys. Rev. E 52, R3337-R3340.Google Scholar
- NGUYEN, Q. C., AND VENKATESWARAN, V. 1993. Implementations of Goldberg-Tarjan maximum flow algorithm. In Network Flows and Matching: First DIMACS Implementation Challenge. D. S. Johnson and C. C. McGeoch, eds. American Mathematical Society, Providence, R.I., pp. 19-42.Google Scholar
- OGmLSKI, A.T. 1986. Integer optimization and zero-temperature fixed point in Ising random-field systems. Phys. Rev. Lett. 57, 1251-1254.Google Scholar
- PHILLIPS, S., AND WESTBROOK, J. 1993. Online load balancing and network flow. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 402-411. Google Scholar
- RoY, S., AND COX, I. 1998. A maximum flow formulation of the N-camera Stereo Correspondence problem. In Proceedings of the International Conference on Computer Vision (Bombay, India, Jan.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 492-499. Google Scholar
- SLEATOR, D. D., AND TARJAN, R.E. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 362-391. Google Scholar
- TARJAN, R.E. 1975. Efficiency of a good but not linear set union algorithm. J. ACM 22, 2 (Apr.), 215-225. Google Scholar
- TARJAN, R.E. 1983. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, Pa. Google Scholar
- VISHKIN, U. 1992. A parallel blocking flow algorithm for acrylic networks. J. Algorithms 13, 489-501. Google Scholar
- WALLACHER, C. 1991. A generalization of the minimum-mean cycle selection rule in cycle canceling algorithms. Tech. Rep. Preprints in Optimization, Institute fiir Angewandte Mathemtik, Technische Universitat Braunschweig, Germany.Google Scholar
- WALLACHER, C., AND ZIMMERMAN, U. 1991. A combinatorial interior point method for network flow problems. Tech Rep. Preprints in Optimization, Institute for Angewandte Mathemtik, Technische Universitat Braunschweig, Germany.Google Scholar
Index Terms
- Beyond the flow decomposition barrier
Recommendations
Flows in undirected unit capacity networks
FOCS '97: Proceedings of the 38th Annual Symposium on Foundations of Computer ScienceWe describe an O(min(m, n/sup 3/2/)m/sup 1/2/)-time algorithm for finding maximum flows in undirected networks with unit capacities and no parallel edges. This improves upon the previous bound of Karzanov and Even and Tarjan when m=/spl omega/(n/sup 3/2/...
Beyond the flow decomposition barrier
FOCS '97: Proceedings of the 38th Annual Symposium on Foundations of Computer ScienceWe introduce a new approach to the maximum flow problem. This approach is based on assigning arc lengths based on the residual flow value and the residual are capacities. Our approach leads to an O(min(n/sup 2/3/, m/sup 1/2/)m log(n/sup 2//m) log U) ...
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computingWe introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear ...
Reviews
Paul Cull
It is always a pleasure to see a breakthrough on an old problem, particularly one that I thought had been resolved. The problem here is to find the maximal flow through a network with n vertices and m edges. As far as I knew, this problem was essentially solved back in the 1960s or early 1970s, and the running time for an algorithm was n×m . As this paper informs me, there has been a reasonable amount of work in the last 30 years, changing the approximately n×m result to precisely n×m . This paper goes further, however. Goldberg and Rao first point out that n×m is not a lower bound for the problem, but is a lower bound for the techniques used in the standard algorithms. They push through this bound to obtain algorithms with running times of about m 2/3 and about m×n 2/3 . The major tricks are collapsing sets of vertices into nodes, and using the wheels-within-wheels and union-find data structures. This is a well-written algorithms paper. A major effort would still be required to produce usable code and to test the practicality of these algorithms.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments