TY - GEN
T1 - An experimental study of minimum mean cycle algorithms
AU - Georgiadis, Loukas
AU - Goldberg, Andrew V.
AU - Tarjan, Robert E.
AU - Werneck, Renato F.
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77950810591&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77950810591&partnerID=8YFLogxK
U2 - 10.1137/1.9781611972894.1
DO - 10.1137/1.9781611972894.1
M3 - Conference contribution
AN - SCOPUS:77950810591
SN - 9780898719307
T3 - 2009 Proceedings of the 11th Workshop on Algorithm Engineering and Experiments, ALENEX 2009
SP - 1
EP - 13
BT - 2009 Proceedings of the 11th Workshop on Algorithm Engineering and Experiments, ALENEX 2009
PB - Society for Industrial and Applied Mathematics Publications
T2 - 11th Annual Workshop on Algorithm Engineering and Experiments, ALENEX 2009
Y2 - 3 January 2009 through 3 January 2009
ER -