@inproceedings{61b49209579b4c1380da25c6b158a949,

title = "An experimental study of minimum mean cycle algorithms",

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.",

author = "Loukas Georgiadis and Goldberg, {Andrew V.} and Tarjan, {Robert E.} and Werneck, {Renato F.}",

year = "2009",

month = jan,

day = "1",

language = "English (US)",

series = "11th Workshop on Algorithm Engineering and Experiments and 6th Workshop on Analytic Algorithmics and Combinatorics 2009, ALENEX 2009/ANALCO 2009",

publisher = "Society for Industrial and Applied Mathematics Publications",

pages = "1--13",

booktitle = "11th Workshop on Algorithm Engineering and Experiments and 6th Workshop on Analytic Algorithmics and Combinatorics 2009, ALENEX 2009/ANALCO 2009",

address = "United States",

note = "11th Workshop on Algorithm Engineering and Experiments, ALENEX 2009 and 6th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2009 ; Conference date: 03-01-2009",

}