COIN-OR::LEMON - Graph Library

Opened 7 years ago

Last modified 6 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 7 years ago by alpar

  • Type changed from task to enhancement

Could you give a citation to this method?

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

comment:2 Changed 7 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 7 years ago by kpeter

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

comment:4 Changed 6 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.