The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily terminate. However, the algorithm does satisfy the following properties.

(1) It can begin in any valid state (any valid flow can be used to initialize Ford-Fulkerson).

(2) At each step of the algorithm, there may be more than one choice, and the algorithm chooses arbitrarily between them (there may be more than one augmenting path, and Ford-Fulkerson chooses one arbitrarily).

(3) If the algorithm does not terminate, it *converges* to a (not necessarily optimal) state (if Ford-Fulkerson does not terminate, it converges to a (not necessarily maximum) flow).

Note that (3) is in contrast to algorithms which do not terminate because they cycle, such as certain pivoting rules of the Simplex algorithm.

Whenever a non-terminating algorithm satisfies the above properties, we can regard it as a *transfinite* algorithm whose run-time is an ordinal number as follows. If a run of the algorithm terminates after a finite number of steps, then its run-time is the corresponding finite ordinal. Otherwise, by (3) it converges to some state $S$. By (1) we can let $\omega$ steps pass and reinitialize the algorithm beginning with $S$. We then recurse. The *(worst-case) ordinal run-time* is the worst run-time over all valid runs of the algorithm (there are multiple possible runs by (2)).

Question.Are there other examples of non-terminating algorithms which satisfy properties (1), (2), and (3)? If so, have their ordinal run-times been analyzed?

In this paper, Spencer Backman and I proved that the ordinal run-time of the Ford-Fulkerson algorithm on a network with $m$ arcs is $\omega^{\Theta(m)}$. The only other example we know of is chip firing on metric graphs, by Backman. We are aware of the work of Hamkins and Lewis on Infinite Time Turing Machines, but as far as we can tell the above question is of a slightly different flavour.

4more comments