Cancelling Most Helpful Total Cuts For Minimum Cost Network Flow

We present a polynomial algorithm for the Minimum Cost Network Flow Problem (MCNF). It is a dual algorithm that is based on cancelling positive augmenting cuts, which are the duals of negative augmenting cycles. We focus on cancelling most helpful total cuts, which are cuts together with augmentation amounts which lead to the maximum possible increase in the dual objective function. We show how to compute a most helpful total cut, and give a rigorous dual conformal decomposition theorem. Cancelling most helpful total cuts is, in spirit, dual to an algorithm of Weintraub as modified by Barahona and Tardos. We also show how our algorithm specializes to the case of shortest s-t path with non-negative distances, show that this specialization is not finite for real data, and show that our bound on the number of cancellations is essentially tight