Implement Young-Tarjan-Orlin algorithm for min mean cycle

[Peter Kovacs]

It would be nice to implement the Young-Tarjan-Orlin algorithm for the minimum mean cycle problem.

According to several survey papers, it is one of the fastest solution methods for this problem (and its extension: the optimum cycle ratio problem). Another method that is highly efficient is Howard's algorithm, which is already implemented in LEMON.

[Alpar Juttner]

Could you give a citation to this method?

For the record, could you give the theoretical running time of Young-Tarjan-Orlin?

[Peter Kovacs]

Here is a citation for the Y-T-O algorithm:

• N. Young, R.E. Tarjan, and J.B. Orlin. Faster Parametric Shortest Path and Minimum Balance Algorithms. Networks, 21:205–221, 1991.

And here are some good survey papers on the topic:

• L. Georgiadis, A.V. Goldberg, R.E. Tarjan, and R.F. Werneck, An Experimental Study of Minimum Mean Cycle Algorithms, in Proc. 6th International Workshop on Algorithm Engineering and Experiments, SIAM, 2009.
• A. Dasdan. Experimental Analysis of the Fastest Optimum Cycle Ratio and Mean Algorithms. ACM Transactions on Design Automation of Electronic Systems, 9(4):385–418, 2004.
• A. Dasdan, S. Irani, and R. K. Gupta. Efficient Algorithms for Optimum Cycle Mean and Optimum Cost to Time Ratio Problem. In Proceedings of the 36th Design Automation Conference, 1999.

[Peter Kovacs]

The YTO algorithm runs in O(nm + n² log(n)) time.