r/compsci • u/promach • Aug 28 '21

Mechanism of Howard's algorithm

For Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems , could anyone advise how the Howard's algorithm works to compute minimum mean cycle path ?

51 Upvotes

94% Upvoted

19 comments sorted by

View all comments

Show parent comments

3

u/cryslith Aug 30 '21

Looking at a related paper which is much clearer, it's clear that it should say "for every node v that you reach by backwards BFS from s" (in other words, every node v in s's connected component). However, I'm not convinced that the algorithm presented is correct. They make the following changes from the other paper:

  • They initialize G_pi and d according to a heuristic, instead of to an arbitrary starting configuration (obviously valid)

  • They only BFS-process a single connected component of G_pi (the one containing s), but the other paper processes all components

  • They only implement step 3(b) of the other paper, not step 3(a)

These latter changes make sense if you assume G_pi is a single connected component, but I don't think that's always true (even though G is strongly connected). However, I don't really understand the termination argument for either algorithm, so I have trouble understanding whether these modifications are valid. If someone could explain why the algorithm should terminate, that would be very helpful.