TIGHT BOUNDS ON THE NUMBER OF MINIMUM-MEAN CYCLE CANCELLATIONS AND RELATED RESULTS

We prove a tight Theta(min(nm log(nC), nm(2))) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg a nd Tarjan [13]. We do this by giving the lower bound and by improving the strongly polynomial upper bound on the number of iterations to O(n m(2)). We also give an improved version of the maximum-mean cut cancel ing algorithm of [7], which is a dual of the minimum-mean cycle-cancel ing algorithm. Our version of the dual algorithm runs in O(nm(2)) iter ations.