Opened 8 years ago
Last modified 7 years ago
#413 new enhancement
Implement Young-Tarjan-Orlin algorithm for min mean cycle
Reported by: | kpeter | Owned by: | alpar |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | core | Version: | hg main |
Keywords: | Cc: | ||
Revision id: |
Description
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.
Change History (4)
comment:1 Changed 8 years ago by alpar
- Type changed from task to enhancement
comment:2 Changed 8 years ago by kpeter
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.
comment:3 Changed 8 years ago by kpeter
The YTO algorithm runs in O(nm + n^{2} log(n)) time.
comment:4 Changed 7 years ago by kpeter
- Summary changed from Young-Tarjan-Orlin algorithm for min mean cycle to Implement Young-Tarjan-Orlin algorithm for min mean cycle
Note: See
TracTickets for help on using
tickets.
Could you give a citation to this method?
For the record, could you give the theoretical running time of Young-Tarjan-Orlin?