Relaxed Most Negative Cycle and Most Positive Cut Canceling Algorithms for Minimum Cost Flow

References

• Ahuja R. K. , Magnanti T. L. , Orlin J. B. Network Flows: Theory, Algorithms, and Applications (1993) (Prentice-Hall, Englewood Cliffs, NJ) Google Scholar
• Ahuja R. K. , Mehlhorn K. , Orlin J. B. , Tarjan R. E. Faster algorithms for the shortest path problem. J. ACM (1990) 37 213 233 Crossref, Google Scholar
• Ahuja R. K. , Orlin J. B. , Tarjan R. E. Improved time bounds for the maximum flow problem. SIAM J. Comput. (1989) 18 939 954 Crossref, Google Scholar
• Armstrong R. D. , Jin Z. A new strongly polynomial dual network simplex algorithm. Math. Programming (1997) 78 131 -148 Crossref, Google Scholar
• Barahona F. , Tardos É. Note on Weintraub's minimum-cost circulation algorithm. SIAM J. Comput. (1989) 18 579 583 Crossref, Google Scholar
• Bellman R. E. On a routing problem. Quart. Appl. Math. (1958) 16 87 90 Crossref, Google Scholar
• Bertsekas D. P. Distributed asynchronous relaxation methods for linear network flow problems. (1986) . Working Paper, Laboratory for Information and Decision Systems, MIT, Cambridge, MA Google Scholar
• Busacker R. G. , Saaty T. L. Finite Graphs and Networks: An Introduction with Applications (1965) (McGraw Hill, New York) Google Scholar
• Cui W. , Fujishige S. A primal algorithm for the submodular flow problem with minimum-mean cycle selection. J. Oper. Res. Soc. Japan (1988) 31 431 440 Google Scholar
• Cunningham W. H. Theoretical properties of the network simplex method. Math. Oper. Res. (1979) 4 196 208 Link, Google Scholar
• Edmonds J. , Karp R. M. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM (1972) 19 248 264 Crossref, Google Scholar
• Engel G. M. , Schneider H. Diagonal similarity and equivalence for matrices over groups with 0. Czech. Math. (1975) 25 389 403 Google Scholar
• Ervolina T. R. , McCormick S. T. Two strongly polynomial cut canceling algorithms for minimum cost network flow. Discrete Appl. Math. (1993a) 46 133 165 Crossref, Google Scholar
• Ervolina T. R. , McCormick S. T. Canceling most helpful total cuts for minimum cost network flow. Networks (1993b) 23 41 52 Crossref, Google Scholar
• Fredman M. L. , Tarjan R. E. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM (1987) 34 596 615 Crossref, Google Scholar
• Fujishige S. Submodular functions and optimization. Annals of Discrete Mathematics (1991) 47 (North-Holland, Amsterdam) Google Scholar
• Fulkerson D. R. An out-of-kilter method for minimum cost flow problems. SIAM J. Appl. Math. (1961) 9 18 27 Crossref, Google Scholar
• Gabow H. N. , Tarjan R. E. Faster scaling algorithms for network problems. SIAM J. Comput. (1989) 18 1013 1036 Crossref, Google Scholar
• Garey M. R. , Johnson D. S. Computers and Intractability, A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Company, New York) Google Scholar
• Gassner B. J. Cycling in the transportation problem. Naval Res. Logist. Quart. (1964) 11 43 58 Crossref, Google Scholar
• Goldberg A. V. Scaling algorithms for the shortest paths problem. SIAM J. Comput. (1995) 24 494 504 Crossref, Google Scholar
• Goldberg A. V. An efficient implementation of a scaling minimum-cost flow algorithm. J. Algorithms (1997) 22 1 29 Crossref, Google Scholar
• Goldberg A. V. , Rao S. Beyond the flow decomposition barrier. J. ACM (1998) 45 753 797 Crossref, Google Scholar
• Goldberg A. V. , Tarjan R. E. A new approach to the maximum flow problem. J. ACM (1988) 35 921 940 Crossref, Google Scholar
• Goldberg A. V. , Tarjan R. E. Finding minimum-cost circulations by canceling negative cycles. J. ACM (1989) 36 873 886 Crossref, Google Scholar
• Goldberg A. V. , Tarjan R. E. Finding minimum-cost circulations by successive approximation. Math. Oper. Res. (1990) 15 430 466 Link, Google Scholar
• Goldfarb D. , Hao J. , Kai S. Anti-stalling pivot rules for the network simplex algorithm. Networks (1990) 20 79 91 Crossref, Google Scholar
• Hadjiat M. Un algorithme fortement polynomial pour la tension de coût minimum basé sur les cocycles de couts moyens minimums. (1994) . Technical Report, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Marseille, France Google Scholar
• Hassin R. The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm. Math. Programming (1983) 25 228 239 Crossref, Google Scholar
• Hassin R. Algorithm for the minimum cost circulation problem based on maximizing the mean improvement. Oper. Res. Letters (1992) 12 227 233 Crossref, Google Scholar
• Hochbaum D. S. , Shanthikumar J. G. Convex separable optimization is not much harder than linear optimization. J. ACM (1990) 37 843 862 Crossref, Google Scholar
• Hoffman A. J. , Bellman R. , Hall M. Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. Proc. of Symposia in Applied Mathematics, Vol. X Combinatorial Analysis (1960) (American Mathematical Society, Providence RI) 113 127 Crossref, Google Scholar
• Iwano K. , Misono S. , Tezuka S. , Fujishige S. A new scaling algorithm for the maximum mean cut problem. Algorithmica (1994) 11 243 255 Crossref, Google Scholar
• Iwata S. , McCormick S. T. , Shigeno M. Fast cycle canceling algorithms for minimum cost submodular flow, submitted to Combinatorica; an extended abstract appears as “A faster algorithm for minimum cost submodular flows”. Proc. Ninth Ann. ACM-SIAM Symposium Discrete Algorithms (1999a) 1998 167 174 Google Scholar
• Iwata S. , McCormick S. T. , Shigeno M. , Cornuéjols G. , Burkard R. E. , Woeginger G. J. A strongly polynomial cut canceling algorithm for minimum cost submodular flow, submitted to SIAM J. on Discrete Math.; an extended abstract appears as “A strongly polynomial cut canceling algorithm for the submodular flow problem”. Proc. Seventh MPS Conf. Integer Programming Combinatorial Optim. (1999b) 259 272 Crossref, Google Scholar
• Iwata S. , McCormick S. T. , Shigeno M. A relaxed cycle-canceling approach to separable convex optimization in unimodular linear space. (1999c) . Manuscript, University of British Columbia, Vancouver, B.C., Canada Google Scholar
• Iwata S. , McCormick S. T. , Shigeno M. A faster primal-dual algorithm for minimum cost submodular flow. Inform. Processing Letters (1999d) . submitted to Google Scholar
• Johnson D. B. A priority queue in which initialization and queue operations take O(log log D) time. Math. Systems Theory (1982) 14 295 309 Google Scholar
• Karp R. M. A characterization of the minimum cycle mean in a digraph. Discrete Math. (1978) 23 309 311 Crossref, Google Scholar
• Karzanov A. V. , McCormick S. T. Polynomial methods for separable convex optimization in totally unimodular linear spaces with applications to circulations and co-circulations in networks. SIAM J. Comput. (1997) 26 1245 1275 Crossref, Google Scholar
• King V. , Rao S. , Tarjan R. A faster deterministic maximum flow algorithm. J. Algorithms (1994) 17 447 474 Crossref, Google Scholar
• Klein M. A primal method for minimal cost flows with applications to the assignment and transportation problems. Management Sci. (1967) 14 205 220 Link, Google Scholar
• McCormick S. T. Approximate binary search algorithms for mean cuts and cycles. Oper. Res. Letters (1993) 14 129 132 Crossref, Google Scholar
• McCormick S. T. , Ervolina T. R. Computing maximum mean cuts. Discrete Appl. Math. (1994) 52 53 70 Crossref, Google Scholar
• McCormick S. T. , Ervolina T. R. , Zhou B. Mean canceling algorithms for general linear programs, and why they (probably) don't work for submodular flow. (1994) . Working Paper 94-MSC-011, UBC Faculty of Commerce, Vancouver, B.C Google Scholar
• McCormick S. T. , Liu L. , Johnson D. S. , McGeoch C. S. An experimental implementation of the dual cancel and tighten algorithm for minimum cost network flow. Network Flows and Matching (1993) 12 247 266 American Mathematical Society DIMACS Series in Discrete Mathematics and Theoretical Computer Science Crossref, Google Scholar
• McCormick S. T. , Shioura A. Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks. OR Letters (1999) . Submitted to Google Scholar
• McCormick S. T. , Schulz A. , Shioura A. , Weismantel R. A Note on an Augmentation Method for Mixed Integer Programming Problems. (1999) . Manuscript, University of British Columbia, Vancouver, B.C., Canada Google Scholar
• Megiddo N. Applying parallel computation algorithms in the design of serial algorithms. J. ACM (1983) 30 852 865 Crossref, Google Scholar
• Minty G. J. Monotone networks. Proc. Royal Soc. London (1960) 257A 194 212 Crossref, Google Scholar
• Orlin J. B. A faster strongly polynomial minimum cost flow algorithm. Oper. Res. (1993) 41 338 350 Link, Google Scholar
• Orlin J. B. A polynomial time primal network simplex algorithm for minimum cost flows. Math. Programming (1997) 78 109 129 Crossref, Google Scholar
• Orlin J. B. , Ahuja R. K. New scaling algorithms for the assignment and minimum cycle mean problems. Math. Programming (1992) 54 41 56 Crossref, Google Scholar
• Orlin J. B. , Plotkin S. , Tardos É. Polynomial dual network simplex algorithms. Math. Programming (1993) 60 255 276 Crossref, Google Scholar
• Phillips S. , Westbrook J. Online load balancing and network flow. Proc. 25th Ann. ACM Symposium on Theory of Comput. (1993) 402 411 Crossref, Google Scholar
• Queyranne M. N. Theoretical efficiency of the algorithm capacity for the maximum flow problem. Math. Oper. Res. (1980) 5 258 266 Link, Google Scholar
• Radzik T. Newton's method for fractional combinatorial optimization. Proc. 33rd IEEE Annual Symp. of Foundations of Computer Science (1992) 659 669 Crossref, Google Scholar
• Pardalos P. Parametric flows, weighted means of cuts, and fractional combinatorial optimization. Complexity in Numerical Optimization (1993) (World Scientific) 351 386 . see also Crossref, Google Scholar
• Radzik T. , Goldberg A. V. Tight bounds on the number of minimum-mean cycle cancellations and related results. Algorithmica (1994) 11 226 242 Crossref, Google Scholar
• Sleator D. D. , Tarjan R. E. A data structure for dynamic trees. J. Comput. System Sci. (1983) 26 362 391 Crossref, Google Scholar
• Tardos É. A strongly polynomial minimum cost circulation algorithm. Combinatorica (1985) 5 247 255 Crossref, Google Scholar
• Tarjan R. E. Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Programming (1997) 78 169 177 Crossref, Google Scholar
• Wallacher C. A generalization of the minimum-mean cycle selection rule in cycle canceling algorithms. (1991) . Report, Inst. Für Ang. Math., Braunschweig Google Scholar
• Weintraub A. A primal algorithm to solve network flow problems with convex costs. Management Sci. (1974) 21 87 97 Link, Google Scholar
• Zadeh N. A bad network problem for the simplex method and other minimum cost flow algorithms. Math. Programming (1973) 5 255 266 Crossref, Google Scholar