Relaxed Most Negative Cycle and Most Positive Cut Canceling Algorithms for Minimum Cost Flow
- 1 February 2000
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 25 (1) , 76-104
Abstract
This paper presents two new scaling algorithms for the minimum cost network flow problem, one a primal cycle canceling algorithm, the other a dual cut canceling algorithm. Both algorithms scale a relaxed optimality parameter, and create a second, inner relaxation. The primal algorithm uses the inner relaxation to cancel a most negative node-disjoint family of cycles w.r.t. the scaled parameter, the dual algorithm uses it to cancel most positive cuts w.r.t. the scaled parameter. We show that in a network with n nodes and m arcs, both algorithms need to cancel only O(mn) objects per scaling phase. Furthermore, we show how to efficiently implement both algorithms to yield weakly polynomial running times that are as fast as any other cycle or cut canceling algorithms. Our algorithms have potential practical advantages compared to some other canceling algorithms as well. Along the way, we give a comprehensive survey of cycle and cut canceling algorithms for min-cost flow. We also clarify the formal duality between cycles and cuts.Keywords
This publication has 52 references indexed in Scilit:
- An Efficient Implementation of a Scaling Minimum-Cost Flow AlgorithmJournal of Algorithms, 1997
- A Faster Deterministic Maximum Flow AlgorithmJournal of Algorithms, 1994
- A new scaling algorithm for the maximum mean cut problemAlgorithmica, 1994
- Tight bounds on the number of minimum-mean cycle cancellations and related resultsAlgorithmica, 1994
- Canceling most helpful total cuts for minimum cost network flowNetworks, 1993
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Applying Parallel Computation Algorithms in the Design of Serial AlgorithmsJournal of the ACM, 1983
- A data structure for dynamic treesJournal of Computer and System Sciences, 1983
- A characterization of the minimum cycle mean in a digraphDiscrete Mathematics, 1978
- Monotone networksProceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1960