Tight bounds on the number of minimum-mean cycle cancellations and related results | Algorithmica Skip to main content
Springer Nature Link
Log in

Tight bounds on the number of minimum-mean cycle cancellations and related results

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We prove a tight Θ(min(nm log(nC), nm2)) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg and Tarjan [13]. We do this by giving the lower bound and by improving the strongly polynomial upper bound on the number of iterations toO(nm 2). We also give an improved version of the maximum-mean cut canceling algorithm of [7], which is a dual of the minimum-mean cycle-canceling algorithm. Our version of the dual algorithm runs in O(nm2) iterations.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. K. Ahuja, A. V. Goldberg, J. B. Orlin, and R. E. Tarjan. Finding Minimum-Cost Flows by Double Scaling. Technical Report STAN-CS-88-1227, Department of Computer Science, Stanford University, 1988.

  2. R. G. Busacker and T. L. Saaty.Finite Graphs and Networks: An Introduction with Applications. McGraw-Hill, New York, 1965.

    Google Scholar 

  3. W. Chi and S. Fujishige. A Primal Algorithm for the Submodular Flow Problem with Minimum-Mean Cycle Selection. Technical Report 350, University of Tsukuba, 1987.

  4. J. Edmonds and R. M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.J. Assoc. Comput. Mach., 19:248–264, 1972.

    Google Scholar 

  5. G. M. Engel and H. Schneider. Diagonal Similarity and Equivalence for Matrices Over Groups with O.Czech. Math. J., 25:389–403, 1975.

    Google Scholar 

  6. T. R. Ervolina and S. T. McCormick. A Strongly Polynomial Dual Cancel and Tighten Algorithm for Minimum Cost Network Flow. Working Paper 90-MSC-010, Faculty of Commerce, University of British Columbia, 1990.

  7. T. R. Ervolina and S. T. McCormick. A Strongly Polynomial Maximum Mean Cut Cancelling Algorithm for Minimum Cost Network Flow. Working Paper 90-MSC-009, Faculty of Commerce, University of British Columbia, 1990.

  8. L. R. Ford, Jr., and D. R. Fulkerson.Flows in Networks. Princeton University Press, Princeton, NJ, 1962.

    Google Scholar 

  9. D. R. Fulkerson. An Out-of-Kilter Method for Minimal Cost Flow Problems.SIAM J. Appl. Math, 9:18–27, 1961.

    Google Scholar 

  10. A. V. Goldberg. Efficient Graph Algorithms for Sequential and Parallel Computers. Ph.D. thesis, M.I.T., January 1987. (Also available as Technical Report TR-374, Laboratory for Computer Science, M.I.T., 1987).

  11. A. V. Goldberg and D. Gusfield. Book Review: by G. M. Adel'son-Vel'ski, E. A. Dinic, and A. V. Karzanov. Technical Report STAN-CS-89-1313, Department of Computer Science, Stanford University, 1990.

  12. A. V. Goldberg, É. Tardos, and R. E. Tarjan. Network Flow Algorithms. Technical Report STAN-CS-89-1252, Department of Computer Science, Stanford University, 1989.

  13. A. V. Goldberg and R. E. Tarjan. Finding Minimum-Cost Circulations by Canceling Negative Cycles.J. Assoc. Comput. Mach., 36:873–886, 1989.

    Google Scholar 

  14. A. V. Goldberg and R. E. Tarjan. Finding Minimum-Cost Circulations by Successive Approximation.Math. Oper. Res., 15:430–466, 1990.

    Google Scholar 

  15. R. Hasin. Algorithms for the Minimum Cost Circulation Problem on Maximizing the Mean Improvement. Unpublished manuscript, School of Mathematical Sciences, Department of Statistics, Tel Aviv University, 1990.

  16. R. Hassin. The Minimum-Cost Flow Problem: A Unifying Approach to Dual Algorithms and a New Tree-Search Algorithm.Math. Programming, 25:228–239, 1983.

    Google Scholar 

  17. K. Iwano, S. Misono, S. Tezuka, and S. Fujishige. A New Scaling Algorithm for the Maximum Mean Cut Problem.Algorithmica, this issue, pp. 243–255.

  18. R. M. Karp. A Characterization of the Minimum Cycle Mean in a Digraph.Discrete Math., 23:309–311, 1978.

    Google Scholar 

  19. M. Klein. A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems.Management Sci., 14:205–220, 1967.

    Google Scholar 

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

    Google Scholar 

  21. S. T. McCormick. A Strongly Polynomial Minimum Mean Cut Algorithm for Submodular Flow. Working Paper 90-MSC-017, Faculty of Commerce, University of British Columbia, 1990.

  22. S. T. McCormick and T. R. Ervolina. Computing Maximum Mean Cuts. Working Paper 90-MSC-011, Faculty of Commerce, 1990. University of British Columbia, 1990.

  23. G. J. Minty. Monotone Networks.Proc. Roy. Soc. London Ser. A, 257:194–212, 1960.

    Google Scholar 

  24. J. B. Orlin. A Faster Strongly Polynomial Minimum Cost Flow Algorithm.Proc. 20th Annual ACM Symposium on Theory of Computing, pp. 377–387, 1988.

  25. J. B. Orlin and R. K. Ahuja. New Scaling Algorithms for Assignment and Minimum Cycle Mean Problems. Sloan Working Paper 2019-88, Sloan School of Management, M.I.T., 1988.

  26. T. Radzik. Minimizing Capacity Violations in a Transshipment Network.Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pp. 185–194, 1992.

  27. É. Tardos. A Strongly Polynomial Minimum Cost Circulation Algorithm.Combinatorica, 5(3):247–255, 1985.

    Google Scholar 

  28. N. Zadeh. A Bad Network Problem for the Simplex Method and Other Minimum Cost Flow Algorithms.Math. Programming, 5:255–266, 1973.

    Google Scholar 

  29. N. Zadeh. More Pathological Examples for Network Flow Problems.Math. Programming, 5:217–224, 1973.

    Google Scholar 

  30. U. Zimmermann. Negative Circuits for Flows and Submodular Flows. Preprints in Optimization Series, Institute Für Angewandte Mathematik, Techniche Universität Caroto-Wilhemina zu Brauschweig, Brauschweig, 1989.

    Google Scholar 

  31. English transcription: G. M. Adel'son-Vel'ski, E. A. Dinic, and A. V. Karzanov,Potokovye Algoritmy, Science, Moscow. Title translation: Flow Algorithms.

  32. English transcription: E. A. Dinic, Metod Porazryadnogo Sokrashcheniya Nevyazok i Transportnye Zadachi,Issledo-vaniya po Diskretnoi Matematike, Science, Moscow. Title translation: The Method of Scaling and Transportation Problems.

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Stanford University, 94305, Stanford, CA, USA

    Tomasz Radzik & Andrew V. Goldberg

Authors
  1. Tomasz Radzik
    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

Additional information

Communicated by Harold N. Gabow.

Partially supported by NSF Presidential Young Investigator Grant CCR-8858097 with matching funds provided by AT&T, IBM Faculty Development Award, and a grant from the 3M Corporation.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Radzik, T., Goldberg, A.V. Tight bounds on the number of minimum-mean cycle cancellations and related results. Algorithmica 11, 226–242 (1994). https://doi.org/10.1007/BF01240734

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Search

Navigation