Name
Abstract | ||
|---|---|---|
We study algorithms for the minimum mean cycle prob- lem, 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 algo- rithms 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 compre- hensive than in previous studies. In our experiments, the tree-based method and two implementations of the cycle-based method outperformed other approaches, in- cluding binary search. |
Year | Venue | Keywords |
|---|---|---|
2009 | ALENEX | shortest path,binary search |
Field | DocType | Citations |
Mathematical optimization,Shortest path problem,Subroutine,Computer science,Algorithm,Implementation,Parametric statistics,Binary search algorithm | Conference | 11 |
PageRank | References | Authors |
0.66 | 9 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Loukas Georgiadis | 1 | 250 | 22.75 |
| Andrew V. Goldberg | 2 | 5883 | 676.30 |
| Robert Endre Tarjan | 3 | 25160 | 6384.61 |
| Renato F. Werneck | 4 | 1743 | 84.33 |