An experimental study of minimum mean cycle algorithms

Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan, Renato F. Werneck

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

We study algorithms for the minimum mean cycle problem, a parametric version of shortest path feasibility (SPF). The three basic approaches to the problem are cycle-based, binary search, and tree-based. The first two use an SPF algorithm as a subroutine, while the latter uses a parametric approach. When implementing the SPF-based methods, one has a choice of SPF algorithms and incremental optimization strategies. There are also several ways to handle precision issues. This leads to dozens of variants, which we systematically compare. Our experimental setup is more comprehensive than in previous studies. In our experiments, the tree-based method and two implementations of the cycle-based method outperformed other approaches, including binary search.

Original languageEnglish (US)
Title of host publication2009 Proceedings of the 11th Workshop on Algorithm Engineering and Experiments, ALENEX 2009
PublisherSociety for Industrial and Applied Mathematics Publications
Pages1-13
Number of pages13
ISBN (Print)9780898719307
DOIs
StatePublished - 2009
Event11th Annual Workshop on Algorithm Engineering and Experiments, ALENEX 2009 - New York, NY, United States
Duration: Jan 3 2009Jan 3 2009

Publication series

Name2009 Proceedings of the 11th Workshop on Algorithm Engineering and Experiments, ALENEX 2009

Other

Other11th Annual Workshop on Algorithm Engineering and Experiments, ALENEX 2009
CountryUnited States
CityNew York, NY
Period1/3/091/3/09

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation

Fingerprint Dive into the research topics of 'An experimental study of minimum mean cycle algorithms'. Together they form a unique fingerprint.

  • Cite this

    Georgiadis, L., Goldberg, A. V., Tarjan, R. E., & Werneck, R. F. (2009). An experimental study of minimum mean cycle algorithms. In 2009 Proceedings of the 11th Workshop on Algorithm Engineering and Experiments, ALENEX 2009 (pp. 1-13). (2009 Proceedings of the 11th Workshop on Algorithm Engineering and Experiments, ALENEX 2009). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611972894.1