id,summary,reporter,owner,description,type,status,priority,milestone,component,version,resolution,keywords,cc,revision
436,Use HartmannOrlinMmc instead of HowardMmc in CycleCanceling,Peter Kovacs,Peter Kovacs,"The min cost flow algorithms implemented in `CycleCanceling` are rather slow in practice, their only advantage is that two of them is proved to be strongly polynomial if the applied min mean cycle algorithm is also strongly polynomial. Although `HowardMmc` is clearly faster than `HartmannOrlinMmc` in practice, its theoretical running time is not polynomial. I think it is more important to ensure that these implementations are indeed strongly polynomial than using Howard's min mean cycle algorithm for efficiency reasons.
Actually, the current state of the library is not consistent. The doc says that two cycle canceling implementations are strongly polynomial and expresses their theoretical running time, while the implementation uses Howard's algorithm, so it is _not_ polynomial. I'm sorry for introducing such an inconsistency.
Therefore, I suggest to use `HartmannOrlinMmc` in the cycle canceling implementations.",enhancement,closed,major,LEMON 1.3 release,core,hg main,fixed,,,