Dual cancelling algorithms and integrality results for network flow problems
Thomas R. Ervolina · 1989
We present a new strongly polynomial algorithm for the Minimum Cost Network Flow Problem (MCNF) which is based on cancelling maximum mean cuts. In addition, we gave a variant called Dual Cancel and Tighten which employs a more flexible cut selection rule and has an overall running time of $O(m\sp{3}n$ log $n)$. These algorithms are dual analogues of the Minimum Mean Cycle Cancelling and (primal) Cancel and Tighten algorithms due to Goldberg and Tarjan. A third dual cancelling algorithm called Most Helpful Cut is presented and shown to have a polynomial running time for instances of MCNF with integer arc costs and bounds. All three of these algorithms do not use scaling to achieve polynomiality. We then generalize the notions of minimum mean cycle and maximum mean cut to general linear programming (LP), thus laying the framework for a minimum mean circuit cancelling algorithm and a Cancel and Tighten algorithm for LP. We also consider the concept of Total Dual Integrality (TDI). We use the Primal-Dual Algorithm to establish a new characterization of TDI systems in terms of Integer Infeasibility Theorems (IIT). We use this result to give a new proof that Edmonds and Giles submodular flow systems are TDI. Finally, we investigate the prospects of developing a minimum mean cut cancelling algorithm for the submodular flow problem (SFP). For the dual of SFP, we are able to show that there must exist 0, $\pm$1 minimum mean co-circuits (cuts). However in the primal, we present a counterexample showing that there may not exist a 0, $\pm$1 maximum mean circuit (cycle). This provides strong evidence that a dual cancelling algorithm may be advantageous over a primal one for SFP and other difficult combinatorial problems which have submodular constraint systems.