Cycle cancellation is a standard textbook algorithm for computing minimum-cost circulations: As long as the residual graph of the current circulation contains a negative cycle, push as much flow along that cycle as possible. I'm trying to understand the worst-case behavior of the generic algorithm. For purposes of analysis, I want to assume that at each iteration, the negative cycle to augment is chosen adversarially.
If all capacities and costs are integers, each iteration decreases the cost of the current circulation by at least 1. Thus, the algorithm halts after augmenting at most $-\$(f^*)$ cycles, where $\$(f^*)$ is the cost of the final circulation. Moreover, standard bad examples for Ford-Fulkerson and the standard reduction from maximum flow to minimum-cost circulation imply that $-\$(f^*)$ iterations are necessary in the worst case.
If we allow irrational capacities, then standard bad examples of Ford-Fulkerson and the standard reduction from maximum flow to minimum-cost circulation imply that the algorithm may never terminate, and worse, may not even converge to an approximate minimum-cost circulation in the limit.
What is known about the case of integer capacities and irrational costs? I have found nothing in the literature about this case.
Cycle cancelling must terminate after a finite number of iterations in this case, because there are only a finite number of feasible integer circulations, but that argument only implies the upper bound $O(U^E)$, where U is the maximum edge capacity. Zadeh's classical bad examples for network simplex (and I suspect similar bad examples for Ford's generic shortest-path algorithm) imply an $\Omega(2^V)$ lower bound, even if the most negative cycle is canceled at each iteration. Are any tighter bounds known?
In particular: What is known about the case of unit capacities and irrational costs?
