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 cancel ling positive augmenting cuts, which are the duals of negative augment ing 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 algorit hms of Goldberg and Tarjan. These algorithms do not use explicit scali ng to achieve polynomiality.