article

Free access

Improved methods for storing and updating information in the out-of-kilter algorithm

Author:

Samar SinghAuthors Info & Claims

Journal of the ACM (JACM), Volume 33, Issue 3

Pages 551 - 567

https://doi.org/10.1145/5925.5934

Published: 01 May 1986 Publication History

Abstract

Currently, network codes based on the primal simplex algorithm are believed to be computationally superior to those based on other methods. Some modifications of the out-of-kilter algorithm of Ford and Fulkerson are given, together with proofs of their correctness and computer implementations using appropriate data structures. The computational tests in this paper indicate that the final code based on these modifications is superior to any previously implemented version of this algorithm. Although this code is not competitive with state-of-the-art primal simplex codes, its performance is encouraging, especially in the case of assignment problems.

References

[1]

AASHTIANI, H. A., AND MAGNANTI, T. L. Implementing primal-dual network flow algorithms. Working Paper OR 055-76, Operations Research Center, Massachusetts Inst. of Technology, Cambridge, Mass. 1976.

[2]

AI,AGIC, S., AND ARBIB, M.A. The Design of H2'll-Structured and Correct Programs. Springer- Verlag, New York, 1978.

[3]

BARR, R. S., GLOVER, F., AND KI,INGMAN, D. An improved version of the out-of-kilter method and a comparative study of computer codes. Math. Prog. 7 ( 1974), 60-86.

[4]

BARR, R. S., GLOVER, F., ANt) KI,INGMAN, D. Enhancements of spanning tree labelling procedures for network optimization. INFOR 17 (1979), 16-33.

[5]

BERTSEKAS, D.P. A new algorithm for the assignment problem. Math. Prog. 21 (1981), 152-171.

[6]

BRADI.EY, G., BROWN, G., AND GRAVES, G. Design and implementation of large-scale primal transshipment algorithms. Management Sci. 24 (1977), 1-35.

[7]

BURKARD, R. E., AND DrRI(;S, U. Assignment and matching problems: Solution methods with Fortran programs. In Lecture Notes in Economics and Mathematical Systems, vol. 184. Springer- Verlag, Berlin, 1980.

[8]

CROWDER, H. P., DEMnO, R. S., AND MULVEY, J. M. Reporting computational experiments in mathematical programming. Math. Prog. 15 (1978), 316-329.

[9]

DEMBO, R. S., AND MUI,VEY, J.M. On the analysis and comparison of mathematical programming algorithms and software. In Computers and Mathematical Programming, W.W. White, Ed. NBS special publication 502, National Bureau of Standards, Washington, D.C., 1978.

[10]

DOURHOUT, B. Het lineare toewijzingsproblem, vergelijking van algorithmen. Rep. BN 21, Stichting Mathematisches Centrum, Amsterdam, 1973.

[11]

EDMONDS, J., AND KARP, R.M. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 2 (Apr. 1972), 248-264.

[12]

ENGQUIST, M. A successive shortest path algorithm for the assignment problem. INFOR 20 (1982), 371-384.

[13]

FORD, L. R., AND FULKERSON, D.R. Flows in Networks. Princeton University Press, Princeton, N.J., 1962.

[14]

GLOVER, F., AND KLINGMAN, D. Comments on a note by Hatch on network algorithms. Oper. Res. 23 (1978), 370-374.

[15]

GI,OVER, F., AND KLINGMAN, D. Recent developments in computer implementation technology for network flow algorithms. INFOR 20 (1982), 435-452.

[16]

GL()VER, F., KARNEY, O., KLINGMAN, D., AND NAPIER, A. A computation study on start procedures, basis change criteria, and solution algorithms for transportation problems. Management Sci. 20 (1974), 793-813.

[17]

GI,OVER, F., KLINGMAN, D., AND STUTZ, J. Augmented threaded index method. INFOR 12 (1974), 293-298.

[18]

HAICH, R.S. Bench marks comparing transportation codes based on primal simplex and primaldual algorithms. Oper. Res. 23 (1978), 1167-1172.

[19]

KENNINGTON, J. L., AND HEI,GASON, R.V. Algorithms for Network Programming. Wiley Interscience, London, 1980.

[20]

KLINGMAN, D., NAPIER, A., AND STUTZ, J. NETGEN: Program for generating large scale capacitated assignment, transportation, and minimum cost network flow problems. Management Sci. 20 (1974), 814-821.

[21]

MCGINNIS, L. F. Implementation and testing of a primal-dual algorithm for the assignment problem. Oper. Res. 31 (1983), 277-291.

[22]

MULVEY, J. M. Testing of a large scale network optimization program. Math. Prog. 15 (1978), 291-314.

[23]

PAPADIMITRIOU, C. H., AND STEIGLITZ, K. H. Combinatorial Optimization. Algorithms and Complevity. Prentice-Hall, Englewood Cliffs, N.J., 1982.

[24]

SCHMIDT, S. R., JENSEN, B. A., AND BARNES, W. J. An advanced dual incremental network algorithm. Networks 12 (1982), 475-492.

[25]

SPERRY UNiVA('. 1100 Series Out-ofiKilter Network Optimization System, UKILT 1100, Level 1R 1. Programmer reference UP-8276, 1976.

[26]

SPFRRV UNIVAC. 1100 Series FORTtL4N V. Programmer Reference UP-4060 Rev. 2, 1976.

[27]

TOMIZAWA, N. On some techniques useful for solution of transportation network problems. Networks 1 (1972), 179-194.

[28]

WIRTH, N. Algorithms + Data Structures= Programs. Prentice-Hall, Englewood Cliffs, N.J., 1976.

[29]

ZADEH, N. A simple alternative to the out-of-kilter algorithm. Tech. Rep. 25, Dept. of Operations Research, Stanford Univ., Stanford, Calif., 1979.

[30]

ZADEH, N. Near-equivalence of network flow algorithms. Tech. Rep. 26, Dept. of Operations Research, Stanford Univ., Stanford, Calif., 1979.

Cited By

Miller-Hooks ETang HChen Z(2018)Updating Network Flows Given Multiple, Heterogeneous Arc Attribute ChangesJournal of Mathematical Modelling and Algorithms10.1007/s10852-010-9129-x9:4(291-309)Online publication date: 11-Dec-2018
https://dl.acm.org/doi/10.1007/s10852-010-9129-x
Bazaraa MJarvis JSherali H(2011)BibliographyLinear Programming and Network Flows10.1002/9780471703778.biblio(681-732)Online publication date: 15-Aug-2011
https://doi.org/10.1002/9780471703778.biblio

Index Terms

Improved methods for storing and updating information in the out-of-kilter algorithm
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

A novel and improved developer rank algorithm for bug assignment

Analytical studies on automatic bug triaging approach have the main objective to recommend appropriate developer for bug report with reduced bug tossing length, time and effort in bug resolution. In bug triaging process, if the first recommended developer ...
Automatic Bug Assignment Using Information Extraction Methods
ACSAT '12: Proceedings of the 2012 International Conference on Advanced Computer Science Applications and Technologies

The number of reported bugs in large open source projects is high and triaging these bugs is an important issue in software maintenance. As a step in the bug triaging process, assigning a new bug to the most appropriate developer to fix it, is not only ...
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

The Random-Facet pivoting rule of Kalai and of Matousek, Sharir and Welzl is an elegant randomized pivoting rule for the simplex algorithm, the classical combinatorial algorithm for solving linear programs (LPs). The expected number of pivoting steps ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 33, Issue 3

July 1986

219 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/5925

Issue’s Table of Contents

Copyright © 1986 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1986

Published in JACM Volume 33, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
596
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)7

Reflects downloads up to 22 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Miller-Hooks ETang HChen Z(2018)Updating Network Flows Given Multiple, Heterogeneous Arc Attribute ChangesJournal of Mathematical Modelling and Algorithms10.1007/s10852-010-9129-x9:4(291-309)Online publication date: 11-Dec-2018
https://dl.acm.org/doi/10.1007/s10852-010-9129-x
Bazaraa MJarvis JSherali H(2011)BibliographyLinear Programming and Network Flows10.1002/9780471703778.biblio(681-732)Online publication date: 15-Aug-2011
https://doi.org/10.1002/9780471703778.biblio

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents