[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Finding minimum-cost flows by double scaling

  • Published:
Mathematical Programming Submit manuscript

Abstract

Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in O(nm(log logU) log(nC)) time on networks withn vertices,m edges, maximum arc capacityU, and maximum arc cost magnitudeC. 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

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.

    Google Scholar 

  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.

    Google Scholar 

  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).

    Google Scholar 

  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).

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  7. H.N. Gabow, “Scaling algorithms for network problems,”Journal of Computer and System Sciences 31 (1985) 148–168.

    Google Scholar 

  8. H.N. Gabow and R.E. Tarjan, “Faster scaling algorithms for networks problems,”SIAM Journal on Computing 18 (1989) 1013–1036.

    Google Scholar 

  9. A.V. Goldberg, “Efficient graph algorithms for sequential and parallel computers,” Ph.D. Thesis, M.I.T. (Cambridge, MA, 1987).

    Google Scholar 

  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.

    Google Scholar 

  11. A.V. Goldberg and R.E. Tarjan, “Finding minimum-cost circulations by successive approximation,”Mathematics of Operations Research 15 (1990) 430–466.

    Google Scholar 

  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.

    Google Scholar 

  13. E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Reinhart and Winston, New York, 1976).

    Google Scholar 

  14. R. Melhorn,Data Structures and Algorithms, Vol. 1: Sorting and Searching (Springer, Berlin, 1984).

    Google Scholar 

  15. J.B. Orlin, “On the simplex algorithm for networks and generalized networks,”Mathematical Programming 23 (1985) 166–178.

    Google Scholar 

  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).

    Google Scholar 

  18. D.D. Sleator and R.E. Tarjan, “A data structure for dynamic trees,”Journal of Computer and System Sciences 26 (1983) 362–391.

    Google Scholar 

  19. D.D. Sleator and R.E. Tarjan, “Self-adjusting binary search trees,”Journal of the Association for Computing Machinery 32 (1985) 652–686.

    Google Scholar 

  20. E. Tardos, “A strongly polynomial minimum cost circulation algorithm,”Combinatorica 5 (1985) 247–255.

    Google Scholar 

  21. R.E. Tarjan,Data Structures and Network Algorithms (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983).

    Google Scholar 

  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.

    Google Scholar 

  23. H.M. Wagner, “On a class of capacitated transportation problems,”Management Science 5 (1959) 304–318.

    Google Scholar 

  24. N. Zadeh, “A bad network flow problem for the simplex method and other minimum cost flow algorithms,”Mathematical Programming 5 (1973) 255–266.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Sloan School of Management, M.I.T., 02139, Cambridge, MA, USA

    Ravindra K. Ahuja & James B. Orlin

  2. Department of Computer Science, Stanford University, 94305, Stanford, CA, USA

    Andrew V. Goldberg

  3. Department of Computer Science, Princeton University, 08544, Princeton, NJ, USA

    Robert E. Tarjan

  4. NEC Research Institute, 08540, Princeton, NJ, USA

    Robert E. Tarjan

Authors
  1. Ravindra K. Ahuja
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrew V. Goldberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. James B. Orlin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Robert E. Tarjan
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research partially supported by an NSF Presidential Young Investigator Fellowship, Contract 8451517ECS, and grants from Analog Devices, Apple Computer Inc., and Prime Computer.

On leave from Indian Institute of Technology, Kanpur, India.

Research partially supported by an NSF Presidential Young Investigator Award.

Research at Princeton University partially supported by National Science Foundation Grant DCR-8605962 and Office of Naval Research Contract N00014-87-K-0467.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ahuja, R.K., Goldberg, A.V., Orlin, J.B. et al. Finding minimum-cost flows by double scaling. Mathematical Programming 53, 243–266 (1992). https://doi.org/10.1007/BF01585705

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01585705

Key words

Search

Navigation