CANCELING 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 canceling positive augmenting cuts, which are the duals of negative augmenting cycles. We focus on canceling most helpful total cuts, which are cuts together with augmentation amounts that 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. Canceling most helpful 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 nonnegative distances, show that this specialization is not finite for real data, and show that our bound on the number of cancellations is essentially tight.