2 STRONGLY POLYNOMIAL CUT CANCELING ALGORITHMS FOR MINIMUM-COST NETWORK FLOW

We present two new strongly polynomial algorithms for the minimum cost network flow problem (MCNF). They are dual algorithms based on cancelling positive augmenting cuts, which are the duals of negative augmenting cycles. The first cancels maximum mean cuts, which are cuts whose increase in the dual objective function per arc is maximum. The second, Dual Cancel and Tighten, employs a more flexible cut selection rule that allows it to be more efficient. These algorithms are duals to the Minimum Mean Cycle Cancelling and (Primal) Cancel and Tighten algorithms of Goldberg and Tarjan. These algorithms do not use explicit scaling to achieve polynomiality.